Graph algorithms: the decision guide + worked problems
◈ 5 cardsWhich traversal / MST / shortest-path algorithm to reach for and why, the relaxation framework, and a verified Dijkstra-vs-Bellman-Ford worked comparison including negative-cycle detection.
Pick the algorithm from the problem (the exam's favorite graph question)
| You are asked for… | Use | Because |
|---|---|---|
| Fewest edges / unweighted shortest path | BFS | layer-by-layer gives δ(s,v) in edges |
| Discovery/finish times, cycle detection | DFS | back edge ⇔ cycle; timestamps drive topo/SCC |
| A valid ordering of a DAG | Topological sort | DFS by decreasing finish time |
| Strongly connected components | DFS + transpose + DFS | second pass in finish order |
| Minimum spanning tree | Kruskal or Prim | both Θ(E lg V); cut property proves both |
| Single-source shortest path, nonneg weights | Dijkstra | greedy EXTRACT-MIN, Θ((V+E) lg V) |
| Single-source, negative edges allowed | Bellman-Ford | Θ(VE); also detects negative cycles |
| Single-source on a DAG (neg OK) | DAG-shortest-paths | Θ(V+E), relax in topo order |
| All-pairs shortest paths | Floyd-Warshall | Θ(V³) DP; Johnson's for sparse |
| Max flow / bipartite matching | Edmonds-Karp | BFS augmenting paths, Θ(VE²) |
The one primitive behind every shortest path: RELAX
Every shortest-path algorithm is just a schedule of relaxations. Bellman-Ford relaxes every edge times (any shortest path has ≤ |V|−1 edges), then one more pass: if any edge still relaxes, there is a negative cycle. Dijkstra relaxes the edges out of the closest-unfinished vertex, once each, in increasing-distance order — which is why it fails on negative edges: a later-discovered negative edge could improve a vertex Dijkstra already finalized. DAG shortest paths relaxes in topological order.
Kruskal vs Prim (both build the MST via the cut property)
The cut property (safe-edge theorem): for any cut that no tree edge yet crosses, the minimum-weight edge crossing it is safe to add. Kruskal applies it edge-centrically — sort edges, add the lightest that does not form a cycle (union-find test). Prim applies it vertex-centrically — grow one tree, always adding the lightest edge leaving it (min-heap keyed by distance-to-tree). Prim is structurally Dijkstra with a different key: Prim keys a fringe vertex by ; Dijkstra keys it by .
Worked comparison (see the exercise)
On a 5-vertex graph with nonnegative weights, Dijkstra and Bellman-Ford must return the same distance vector [0, 7, 3, 9, 5]. Add an edge of weight and a negative cycle appears — Bellman-Ford's detection pass returns None, while Dijkstra would silently return garbage. That contrast is the exam's point.