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

The implementation of Floyd-Warshall is relatively straightforward compared to Dijkstra’s algorithm. We’ll construct the matrices $A_0, P_0$ from the weighted adjacency list and then iteratively compute the distance and predecessor matrices $A_k, P_k$, for $k = 1, \ldots, |V|$.

One important observation to reduce the memory footprint of the algorithm is that the computation of $A_{k+1}$ and $P_{k+1}$ depends only on the immediate previous matrices $A_k$ and $P_k$. Therefore, the updates to the distance and predecessor matrices can be done in place. In other words,, we only need to store one pair of $n \times n$ matrices instead of all of them. This reduces the memory requirements from $\mathcal{O}(|V|^3)$ to $\mathcal{O}(|V|^2)$.

Another implementation detail is how to represent the infinite values in the distance matrices. A pragmatic and often feasible solution is to use a large constant value such as one billion to represent infinity. The main concern here is that this value should be larger than the maximum length of a shortest path in the graph, to avoid overflows or incorrect results.

# Implementation notes

The implementation of Floyd-Warshall is relatively straightforward compared to Dijkstra’s algorithm. We’ll construct the matrices $A_0, P_0$ from the weighted adjacency list and then iteratively compute the distance and predecessor matrices $A_k, P_k$, for $k = 1, \ldots, |V|$.

One important observation to reduce the memory footprint of the algorithm is that the computation of $A_{k+1}$ and $P_{k+1}$ depends only on the immediate previous matrices $A_k$ and $P_k$. Therefore, the updates to the distance and predecessor matrices can be done in place. In other words,, we only need to store one pair of $n \times n$ matrices instead of all of them. This reduces the memory requirements from $\mathcal{O}(|V|^3)$ to $\mathcal{O}(|V|^2)$.

Another implementation detail is how to represent the infinite values in the distance matrices. A pragmatic and often feasible solution is to use a large constant value such as one billion to represent infinity. The main concern here is that this value should be larger than the maximum length of a shortest path in the graph, to avoid overflows or incorrect results.

Learn about the details of implementing Floyd-Warshall.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Implementation of Floyd-Warshall

Implementation notes