Start learning →

Graph algorithms

Putting tasks in a valid order, finding shortest paths with and without negative edges, and connecting every vertex as cheaply as possible.

About 9 hours of study

Learning objectives

Lessons

  1. 1

    Topological sort

    Order the tasks of a directed acyclic graph so every task comes after the ones it depends on, with Kahn's algorithm.

  2. 2

    Shortest paths: Dijkstra and Floyd–Warshall

    The cheapest route on a weighted graph: Dijkstra from one start vertex, Floyd–Warshall between every pair.

  3. 3

    Minimum spanning trees

    Join every vertex at the smallest total cost: Kruskal with union-find, and Prim growing one tree.

Module practice

Module quiz

1. When does a directed graph have a topological order?
2. What is the in-degree of a vertex?
3. The edges are 0→1, 0→2, 1→3 and 2→3. Which is a topological order?
4. A graph has the edges 0–1 with weight 4, 0–2 with weight 1 and 1–2 with weight 2. What is the weight of its minimum spanning tree?
5. In Floyd–Warshall, which loop has to be the outermost?
6. How many rounds of relaxing every edge does Bellman–Ford need on n vertices when there is no negative cycle?
7. In a minimum spanning tree of a road map, is the route between two cities always the shortest route between them?

‹ Backtracking, greedy and dynamic programmingNumbers and recurrences ›