Graph Algorithms

Graph algorithms look like a long list of unrelated procedures with unrelated proofs. They are better seen as variations on one shape.

Every algorithm in this chapter visits vertices and edges, and attaches bookkeeping to that visit. Breadth-first search records a discovery order. Dijkstra records a tentative distance. Kruskal records which components have merged. Floyd-Warshall records which intermediate vertices have been permitted.

What distinguishes them is what the bookkeeping records and, crucially, when it dares to declare something final. A greedy algorithm finalises early and needs a proof that it is safe to do so; a dynamic program finalises late and pays for the caution in running time.

That single distinction explains the whole chapter's structure of preconditions. Dijkstra finalises a vertex the moment it is closest, so a negative edge could invalidate that decision and is forbidden. Bellman-Ford never finalises until the last pass, so it tolerates negative edges and costs more.

The second organising fact is that almost every cost here is $O(V+E)$ or a small factor above it. A traversal is linear; adding a priority queue costs a logarithm; considering all pairs costs a factor of $V$. Knowing which of those three a problem needs is most of the complexity question.

1. Traversal and Its Immediate Consequences

Breadth-first and depth-first search both cost $O(V+E)$ with adjacency lists, and both visit every reachable vertex once.

Breadth-first search uses a queue and yields shortest paths in unweighted graphs, because it expands one distance layer at a time.

Depth-first search uses a stack and yields structural information: discovery and finishing times, and an edge classification into tree, back, forward and cross edges.

Three problems follow almost directly from a traversal.

Connected components are found by running a traversal from each unvisited vertex and counting the restarts.

Cycle detection in a directed graph is the presence of a back edge. In an undirected graph, it is any edge to a visited vertex other than the immediate parent.

Topological sorting of a directed acyclic graph has two standard formulations.

The depth-first version lists vertices in decreasing order of finishing time. The correctness argument is short: for any edge from $u$ to $v$ in an acyclic graph, $u$ must finish after $v$, so $u$ precedes $v$ in the reversed order.

Kahn's algorithm is the iterative version: repeatedly remove a vertex of in-degree zero and decrement its neighbours' in-degrees. If vertices remain when no in-degree-zero vertex exists, the graph has a cycle, which makes it a cycle detector as well.

A topological order is not unique unless the graph has a Hamiltonian path, and counting the valid orders is a separate and harder problem.

2. Minimum Spanning Trees

A minimum spanning tree connects every vertex with the least total edge weight, using exactly $V-1$ edges.

Two properties justify every MST algorithm.

The cut property: for any partition of the vertices into two sets, the minimum-weight edge crossing the partition belongs to some minimum spanning tree.

The cycle property: for any cycle, the maximum-weight edge in that cycle belongs to no minimum spanning tree.

Kruskal's algorithm sorts all edges by weight and adds each one that does not create a cycle, using a union-find structure to test connectivity. Sorting dominates, giving $O(E\log E)$, which is $O(E\log V)$ since $E<V^2$.

Prim's algorithm grows a single tree from an arbitrary start, repeatedly adding its cheapest outgoing edge. With a binary heap it costs $O(E\log V)$; with a simple array it costs $O(V^2)$, which is better for dense graphs.

The minimum spanning tree is unique if all edge weights are distinct. With repeated weights several trees may tie, though the total weight is of course the same for all of them.

Adding a constant to every edge weight does not change the MST, since every spanning tree has exactly $V-1$ edges and all totals shift equally. Multiplying does not change it either, provided the constant is positive.

Kruskal's algorithm depends entirely on a union-find structure, which maintains disjoint sets under two operations: find the representative of an element's set, and union two sets.

The naive implementation is a forest of trees where each node points at its parent, and find walks to the root. Without optimisation a tree can degenerate into a chain and find costs $O(n)$.

Two optimisations fix this and are examined together.

Union by rank attaches the shorter tree under the taller one, which keeps the height logarithmic because a tree of height $h$ requires at least $2^h$ nodes.

Path compression flattens the path during a find, repointing every node visited directly at the root, so subsequent finds on those nodes are immediate.

With both, the amortised cost per operation is effectively constant — formally the inverse Ackermann function, which is at most 4 for any input that will ever be constructed. This is why Kruskal's cost is dominated by the sort rather than by the connectivity tests.

3. Single-Source Shortest Paths

Three algorithms address progressively harder cases.

Breadth-first search solves the unweighted case in $O(V+E)$.

Dijkstra's algorithm handles non-negative weights. It maintains tentative distances, repeatedly finalises the closest unfinalised vertex, and relaxes its outgoing edges. With a binary heap the cost is $O((V+E)\log V)$.

The non-negativity requirement is not a technicality. Finalising the closest vertex is safe only because no later path can arrive more cheaply, and that argument depends on every subsequent edge being non-negative.

Bellman-Ford handles negative weights. It relaxes every edge $V-1$ times, which suffices because any shortest path has at most $V-1$ edges, and costs $O(VE)$.

A $V$-th pass that still improves some distance proves a negative cycle exists, which is the standard detection method and something Dijkstra cannot do at all.

On a directed acyclic graph, shortest paths are computable in $O(V+E)$ by relaxing edges in topological order — faster than Dijkstra and correct even with negative weights, since the acyclicity removes the difficulty.

4. All-Pairs Shortest Paths

Floyd-Warshall is a dynamic program over which vertices are permitted as intermediates.

$d_{ij}^{(k)}=\min (d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$

The outermost loop must be over $k$, the intermediate vertex, and putting it inside gives wrong answers. This is the single most examined implementation detail in the chapter.

The cost is $O(V^3)$ with $O(V^2)$ space, it handles negative edges, and a negative value on the diagonal after completion signals a negative cycle.

Running Dijkstra from every vertex costs $O(V(V+E)\log V)$, which beats Floyd-Warshall on sparse graphs but requires non-negative weights.

Johnson's algorithm removes that restriction by reweighting the graph with Bellman-Ford so that all weights become non-negative while preserving shortest paths, then running Dijkstra from each vertex. It costs $O(V^2\log V+VE)$ and is the method of choice for sparse graphs with negative edges.

5. Why the Preconditions Exist

Each restriction traces back to what the algorithm finalises and when.

Dijkstra forbids negative edges because it declares a vertex final the moment it is closest. A negative edge discovered later could reduce that distance, and nothing would revisit it.

Bellman-Ford permits them because it finalises nothing until all passes complete, so a late improvement is still incorporated.

Neither handles a negative cycle meaningfully, because a path can circle it repeatedly and reduce its cost without bound, so no shortest path exists. Bellman-Ford's contribution is to detect this rather than to solve it.

Prim and Kruskal permit negative weights freely, because a spanning tree must contain exactly $V-1$ edges regardless of sign, so there is no incentive to circle anything.

Floyd-Warshall permits negative edges because it considers every intermediate vertex systematically rather than committing early.

6. Complexity Summary

Kosaraju's algorithm finds strongly connected components with two depth-first searches: one on the graph to record finishing times, and one on the transpose in decreasing order of those times. Each tree in the second search is one component.

Why the transpose works is worth a sentence: reversing every edge leaves the strongly connected components unchanged, since mutual reachability is symmetric, but it prevents the second search from escaping a component into one that finishes later.

Contracting each strongly connected component to a single vertex yields the condensation, which is always a directed acyclic graph — because a cycle among components would merge them into one.

7. Choosing an Algorithm

The selection procedure is short and mechanical.

Ask first whether the graph is weighted. If not, breadth-first search answers shortest paths in linear time and nothing more elaborate is needed.

Then ask whether any weight is negative. If none is, Dijkstra applies. If some are, Bellman-Ford is required, and if the graph is additionally acyclic, topological relaxation is faster than both.

Then ask whether one source or all pairs is needed. All pairs on a dense graph favours Floyd-Warshall at $O(V^3)$; all pairs on a sparse graph favours repeated Dijkstra, or Johnson's if negative edges are present.

8. Worked Examples

Example 1. A weighted undirected graph has edges AB=4, AC=3, BC=1, BD=2, CD=5, DE=6. Find a minimum spanning tree using Kruskal's algorithm.

Sort the edges by weight: BC=1, BD=2, AC=3, AB=4, CD=5, DE=6.

BC=1: A, B, C, D, E are all separate. Adding BC creates no cycle. Accept. Components: {B,C}, {A}, {D}, {E}.

BD=2: B and D are in different components. Accept. Components: {B,C,D}, {A}, {E}.

AC=3: A and C are in different components. Accept. Components: {A,B,C,D}, {E}.

AB=4: A and B are now in the same component, so this would create a cycle. Reject.

CD=5: C and D are in the same component. Reject.

DE=6: D and E are in different components. Accept. Components: {A,B,C,D,E}.

The tree is BC, BD, AC, DE with total weight $1+2+3+6=12$, using exactly $V-1=4$ edges.

Note the cycle property at work. Edge AB was rejected as the heaviest edge on the cycle A-B-C-A, and CD as the heaviest on B-C-D-B. Both are exactly what the cycle property predicts.

Example 2. Run Dijkstra's algorithm from S on a directed graph with edges S→A=4, S→B=1, B→A=2, A→C=5, B→C=8.

Initialise: distance to S is 0, all others infinite.

Finalise S (distance 0). Relax its edges: A becomes 4, B becomes 1.

The closest unfinalised vertex is B at 1. Finalise it. Relax B's edges: A via B is $1+2=3$, which improves on 4, so A becomes 3. C via B is $1+8=9$, so C becomes 9.

The closest unfinalised is A at 3. Finalise it. Relax A's edge: C via A is $3+5=8$, which improves on 9, so C becomes 8.

Finalise C at 8.

Final distances: S=0, B=1, A=3, C=8.

The instructive step is A being improved from 4 to 3 after B was finalised. Dijkstra's guarantee is only that a finalised distance is correct; tentative distances are revised freely until the vertex is chosen.

Example 3. Why does Dijkstra fail on this graph: S→A=2, S→B=5, B→A=−4?

Initialise S at 0. Relax: A becomes 2, B becomes 5.

The closest unfinalised vertex is A at 2, so Dijkstra finalises A at distance 2 and never reconsiders it.

Then B is finalised at 5, and relaxing B→A would give $5+(-4)=1$ — but A is already final, so the improvement is discarded.

Dijkstra reports 2; the true shortest distance to A is 1, via S→B→A.

The failure is structural, not a bug. Dijkstra's correctness proof states that when a vertex is chosen as closest, no path through any other unfinalised vertex can be shorter, because such a path must first reach that vertex at distance at least as great and then travel non-negative edges. The negative edge breaks the second clause exactly.

Bellman-Ford would handle this: after enough passes, the relaxation of B→A would reduce A to 1, because it finalises nothing early.

Example 4. Run Bellman-Ford on a graph with 4 vertices and detect whether a negative cycle exists. Edges: A→B=1, B→C=−3, C→D=2, D→B=1.

Source A, distances initialised to 0 for A and infinite elsewhere. Relax all edges $V-1=3$ times.

Pass 1: A→B gives B=1. B→C gives C=$1-3=-2$. C→D gives D=$-2+2=0$. D→B gives B=$0+1=1$, no change.

Pass 2: A→B no change. B→C gives C=$1-3=-2$, no change. C→D gives D=0, no change. D→B gives 1, no change.

Pass 3: No changes.

Now the $V$-th check pass: relax every edge once more and see whether anything improves. Nothing does.

No negative cycle exists. The cycle B→C→D→B has weight $-3+2+1=0$, which is non-negative, so circling it gains nothing.

Change C→D to weight 1, making the cycle weight $-3+1+1=-1$. Now every pass would reduce B, C and D by 1, and the check pass would still improve them — proving a negative cycle.

The detection rule is exactly this: if any distance still improves on a $V$-th pass, a negative cycle is reachable from the source.

Example 5. Why must Floyd-Warshall's outermost loop be over the intermediate vertex $k$?

The recurrence computes $d_{ij}^{(k)}$, the shortest path from $i$ to $j$ using only vertices $1$ through $k$ as intermediates.

Computing it requires both $d_{ik}^{(k-1)}$ and $d_{kj}^{(k-1)}$ — the best paths to and from $k$ using only the first $k-1$ intermediates — to be already correct.

Looping over $k$ outermost guarantees this, because the entire table for level $k-1$ is complete before any level-$k$ entry is computed.

If $k$ were the inner loop, then for a fixed pair $(i,j)$ the algorithm would try all intermediates before moving to the next pair. But a path from $i$ to $j$ through $k$ may itself need to route through some vertex $m$ that has not been considered for the sub-paths yet, so the value used for $d_{ik}$ would be stale.

Concretely, with a path $1\to 3\to 2\to 4$, computing $d_{14}$ with $k$ innermost might consider intermediate 3 before $d_{34}$ has learned about intermediate 2, and record a longer distance that is never corrected.

The looping order is the algorithm's correctness argument made executable, which is why it is the most examined implementation detail here.

Example 6. A graph has 6 vertices and 10 edges with distinct weights. How many edges does its MST have, is it unique, and does adding 5 to every weight change it?

An MST on $V$ vertices always has exactly $V-1$ edges, so 5 edges.

Since all weights are distinct, the MST is unique. The argument is by contradiction: if two distinct MSTs existed, take the lightest edge in one but not the other, and adding it to the second creates a cycle whose other edges are all heavier; removing the heaviest of those gives a lighter spanning tree, contradicting minimality.

Adding 5 to every edge weight does not change which tree is minimum. Every spanning tree contains exactly 5 edges, so every total rises by exactly 25, and the ordering of totals is preserved.

The same is not true for shortest paths. Paths have different edge counts, so adding a constant penalises long paths more than short ones and can change which path is shortest. That asymmetry between MST and shortest path is a standard exam contrast.

Summary

Every algorithm here is a traversal with bookkeeping, and what distinguishes them is what they record and when they dare to finalise.

BFS and DFS both cost $O(V+E)$. BFS gives unweighted shortest paths; DFS gives discovery times, finishing times and edge classification.

Topological sorting is reverse DFS finishing order, or Kahn's repeated removal of in-degree-zero vertices, which doubles as a cycle detector.

MSTs are justified by the cut and cycle properties. Kruskal sorts edges and uses union-find; Prim grows one tree with a priority queue. Both cost $O(E\log V)$, and Prim with an array is better on dense graphs.

An MST is unique when all weights are distinct, has exactly $V-1$ edges, and is unchanged by adding or positively scaling every weight.

Dijkstra finalises the closest vertex and therefore forbids negative edges. Bellman-Ford relaxes every edge $V-1$ times, tolerates negative edges, and detects negative cycles by a $V$-th pass that still improves.

Shortest paths on a DAG take $O(V+E)$ by relaxing in topological order, and work with negative weights.

Floyd-Warshall is a dynamic program over permitted intermediates with the $k$ loop outermost, costing $O(V^3)$ and detecting negative cycles on the diagonal. Johnson's reweights with Bellman-Ford and then runs Dijkstra everywhere, which suits sparse graphs with negative edges.

Adding a constant to every edge preserves the MST but can change the shortest path, because spanning trees have equal edge counts and paths do not.