Explore the basics of graph theory, learn to represent graphs in C++, and master essential algorithms like DFS and Dijkstra to solve complex optimization problems, including matching and network flow.

Graph algorithms are the core of many real-world applications of computer science,  such as automotive navigation or routing in computer networks. They’re also a common subject in coding interviews at top-tier tech companies.
 
In this course, we’ll learn about the basic concepts of graph theory and how to represent graphs as data structures in code. We’ll study essential graph algorithms such as depth-first search or Dijkstra's algorithm to traverse graphs and find shortest paths. Finally, we’ll learn to solve more complex optimization problems on graphs, such as matching and network flow problems.

Learn Graph Algorithms in C++

## Implementation notes

As we saw in the previous lesson, Dijkstra’s algorithm is very similar to BFS in the sense that the closest unexplored node is processed next within the order of processing. However, determining the closest node needs to consider the distance estimates known so far, and that they can change over time. Therefore, it is not possible to simply store the unfinished nodes in a static queue data structure.

A naive implementation could simply store the currently known distance of each node in a `vector` and check all the unexplored nodes during each iteration to get the node with the minimum distance. However, this would lead to a time complexity of 
$\mathcal{O}(|V|^2)$, and we can do better.

Instead, we should use a data structure that allows us to efficiently get the node with the lowest distance estimate. Additionally, the data structure should support updating the distance estimate of a vertex. Both properties can be fulfilled by using a **priority queue** data structure to store the nodes and their distances. 

The following illustration shows how such a priority queue looks during the execution of Dijkstra's algorithm:

# Implementation notes

As we saw in the previous lesson, Dijkstra’s algorithm is very similar to BFS in the sense that the closest unexplored node is processed next within the order of processing. However, determining the closest node needs to consider the distance estimates known so far, and that they can change over time. Therefore, it is not possible to simply store the unfinished nodes in a static queue data structure.

A naive implementation could simply store the currently known distance of each node in a `vector` and check all the unexplored nodes during each iteration to get the node with the minimum distance. However, this would lead to a time complexity of 
$\mathcal{O}(|V|^2)$, and we can do better.

Instead, we should use a data structure that allows us to efficiently get the node with the lowest distance estimate. Additionally, the data structure should support updating the distance estimate of a vertex. Both properties can be fulfilled by using a **priority queue** data structure to store the nodes and their distances. 

The following illustration shows how such a priority queue looks during the execution of Dijkstra's algorithm:

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Implementation of Dijkstra

Implementation notes