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++

In the next lessons, we’ll focus on the All Sources Shortest Path (ASSP) problem. Of course, we could solve the ASSP problem by just running Dijkstra’s algorithm once from each starting vertex. But the Floyd-Warshall algorithm, which was designed to specifically solve the ASSP problem, is a viable alternative. Its benefits are that it is very simple to implement and it runs faster than repeated Dijkstra executions on dense graphs.

# The Floyd-Warshall algorithm

To explain how the Floyd-Warshall algorithm works, let's look at a small example graph.


Use Floyd-Warshall to compute shortest paths between all pairs of nodes.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Floyd-Warshall Algorithm for the ASSP

The Floyd-Warshall algorithm