Motivation
Several graph algorithms repeatedly select a vertex or an edge, yet their proofs protect different meanings. Breadth-first search certifies distances in numbers of edges. A minimum spanning tree minimizes a total cost connecting every vertex. Dijkstra's algorithm certifies distances from a source. Confusing these objectives can produce an algorithm that looks reasonable but solves a different problem.
We use finite simple graphs with vertex set , edge set , and adjacency lists. A directed edge is an ordered pair; an undirected edge is examined at each endpoint. A path has no repeated vertices, while a walk may repeat vertices. Weighted claims use exact real addition and comparison as unit-cost operations; long-integer or finite-precision arithmetic requires additional accounting. Write and .
Definitions
Definition 3.2.1
(Traversal and distance)
A vertex is reachable from source if a directed path from exists, respecting edge directions. In an undirected graph, each edge may be traversed either way. Unweighted distance is the fewest edges in such a path, with infinity for an unreachable vertex. Weighted distance is the infimum of source-to-vertex walk weights, with positive infinity when no walk exists and negative infinity when their weights are unbounded below. A reachable negative cycle can make the distances of suitable reachable vertices negative infinity.
Definition 3.2.2
(Trees, cuts, and relaxation)
For a connected undirected graph, a spanning tree is a connected acyclic subgraph containing all vertices. A minimum spanning tree, or MST, has smallest total edge weight among spanning trees. A cut is a partition into a nonempty vertex subset and its nonempty complement. An edge crosses it when its endpoints lie on different sides. Relaxing a directed edge replaces a tentative distance by , ignoring an infinite .
A connected acyclic graph has a unique path between each pair of vertices: two different paths would contain a cycle. Removing an edge of a tree disconnects it, and adding one new edge creates exactly the cycle formed by that edge and the old unique path. These elementary facts support the exchange proof below. An MST need not be unique when weights tie, and negative weights are allowed for MST problems.
Theorems
Theorem 3.2.3
(Traversal guarantees)
Breadth-first search, or BFS, marks a vertex when first enqueued and processes a first-in-first-out queue. Starting with distance zero at , it assigns a newly discovered neighbor distance one greater than the current vertex. These distances are the unweighted shortest-path distances, and all reachable vertices are found in time.
Depth-first search, or DFS, recursively explores each previously unvisited neighbor before finishing its current vertex. A full DFS forest takes time. In a directed acyclic graph, reversing the order in which vertices finish gives a topological ordering: every edge points forward.
Theorem 3.2.4
(The cut exchange and Kruskal's algorithm)
Suppose a forest is contained in some MST, and a cut has no crossing edge in . A minimum-weight edge crossing that cut can be added to while preserving containment in some MST. Consequently Kruskal's algorithm, scanning edges in nondecreasing weight and accepting an edge exactly when its endpoints are in different current components, constructs an MST of a connected undirected graph.
Theorem 3.2.5
(Dijkstra's finalization rule)
If every edge weight is nonnegative, initialize , all other distances infinite, and repeatedly finalize an unfinalized vertex with smallest finite distance, relaxing its outgoing edges. Every finalized value is the true shortest-path distance. When no finite unfinalized value remains, all remaining vertices are unreachable.
Theorem 3.2.6
(Bellman–Ford with negative edges)
Suppose no negative cycle is reachable from . Then after passes that relax every edge, the labels equal the true distances, in time. A further pass can lower a label exactly when a negative cycle is reachable from .
Proof sketch or proof idea
Proof
(BFS discovers vertices in distance order)
BFS records actual paths: a discovered vertex receives the current vertex's path followed by one edge. Queue order processes vertices in nondecreasing assigned distance. Initially the queue contains only distance zero. Processing a distance- vertex appends only distance- vertices after all already queued vertices, whose distances are or . This proves the order inductively. Suppose a vertex first receives distance greater than its actual minimum. On a shortest source path, take the first vertex whose discovery fails to attain its true distance. Its predecessor has the correct smaller distance and is processed before any vertex that could give the alleged longer discovery. It would discover that vertex with the correct distance, a contradiction. Reachability follows because a first undiscovered vertex on any reachable path would have a discovered predecessor that eventually examines the edge to it.
Marking at enqueue time ensures each vertex enters the queue at most once. Every adjacency entry is examined once, yielding the stated time, including initialization and possibly disconnected input storage. Predecessor pointers reconstruct a shortest path; they form a discovery tree on reachable vertices. BFS on a weighted graph still minimizes the number of edges, which need not minimize total weight.
What a DFS finish time certifies
Proof
(Reverse finish order is topological)
Use three colors: white before discovery, gray while active in the recursive call stack, and black after finishing. A gray neighbor reached by a directed edge is an ancestor in the active stack, so the stack path together with this edge gives a directed cycle. In a directed acyclic graph, no such edge exists. For any edge , when DFS examines it, a white is recursively completed before , while a black has already finished. A gray is impossible in a DAG. Therefore every edge has the finish of before the finish of , proving that reverse finish order is topological.
Starting DFS again at each remaining white vertex covers disconnected graphs and all directed components. Each vertex changes color only once in each direction and each adjacency entry is examined once, so the traversal is linear. For undirected cycle detection the edge to the parent needs separate treatment; the directed gray-edge criterion cannot be copied without that qualification.
Counterexample mode
A gray neighbor in an undirected graph
Consider the claim that in an undirected graph, meeting a gray neighbor during DFS proves that a cycle exists. Take a graph with the single edge and start DFS at . It discovers , and from the edge to is examined while is gray. The supposed cycle would be , but the graph has no cycle at all. The edge back to the parent is the same undirected edge, not a second one. The repaired criterion for simple undirected graphs ignores the tree edge to the parent: a gray neighbor that is not the parent, reached by a different edge, does give a cycle.
The MST exchange
Proof
(A lightest crossing edge is safe)
Let be an MST containing , and let be a lightest crossing edge. If , there is nothing to prove. Otherwise add to , creating a unique cycle. The old path between its endpoints crosses the cut, so the cycle contains another crossing edge . No crossing edge lies in , hence . Removing restores a spanning tree containing . Since , the new tree has weight no greater than the optimal tree , so it is itself optimal. This proves the safe-edge assertion even when equal weights occur.
Proof X-ray
Why the swapped edge exists and is harmless
The exchange is a one-edge swap, and it rests on two cut facts. Adding to the tree closes a cycle through , and a cycle that crosses a cut once must cross it again, so the edge exists. Because no edge of crosses the cut, , so removing keeps inside the new tree. The inequality is the only place where lightness is used, and it makes the new tree no heavier. Dropping the condition on would allow and the swap could destroy containment. Dropping lightness would allow and the tree could become heavier. Only is needed, which is why ties are harmless.
Proof
(Kruskal's algorithm builds an MST)
Initially Kruskal's empty forest is contained in an MST. For an accepted edge, take the cut formed by one of its current components. No accepted edge crosses it. The edge is lightest across this cut: any strictly lighter crossing edge would have been processed earlier and accepted then, since its endpoints, still in different components now, were also in different components then. Thus the safe-edge assertion preserves the invariant. Each accepted edge joins components and never creates a cycle. If more than one component remained after every edge was scanned, connectedness would supply an edge between components that should have been accepted. The final forest is therefore connected and is an MST.
To implement components without assuming a sophisticated amortized theorem, use parent-pointer trees and attach the smaller component's root below the larger component's root. Each increase in a vertex's depth at least doubles the size of its component, so depth is at most . Finding roots and uniting components therefore take time per processed edge. Sorting costs ; for a simple graph, , giving total time and storage. A path-compression improvement is outside this proof.
Why Dijkstra needs nonnegative edges
Proof
(Dijkstra finalizes true distances)
Every finite tentative distance is the weight of an actual source walk, so it is at least the optimum distance whenever an optimum exists. With nonnegative weights, cycles can be removed without increasing cost, so a shortest path exists for every reachable vertex. Assume all earlier finalizations are correct, and let be the next vertex selected. On a shortest path to , let be the first unfinalized vertex. If , its tentative value is zero. Otherwise its predecessor is finalized, so relaxing already gave no greater than the shortest-path prefix weight to . Shortest-path prefixes are optimal, since replacing a prefix by a better one would improve the complete walk and then allow cycle removal.
Nonnegativity makes that prefix weight at most the complete distance to . Minimal selection gives , while the actual-walk property gives the reverse inequality. Thus is finalized correctly. If some reachable vertex remained but all unfinalized distances were infinite, the first unfinalized vertex on a reachable path would have a finite tentative distance from its finalized predecessor, a contradiction.
Proof X-ray
The first unfinalized vertex on the path
The proof cannot compare with its predecessor on a shortest path, because that predecessor may itself be unfinalized. The key move is to choose , the first unfinalized vertex on the path. Its predecessor is finalized, so relaxation has already given the weight of the path prefix. Nonnegativity is used exactly once, to say that this prefix weighs no more than the whole path, which gives . A negative edge after could make the whole path lighter than its prefix, and the inequality fails. The minimal choice of gives , and the fact that every finite label is an actual walk weight gives .
Scanning all unfinalized vertices to select the minimum gives time and distance/parent storage beyond adjacency lists. A binary heap can improve the bound, but requires its own operation-cost analysis; correctness of the distance invariant is independent of the particular priority-queue implementation. Distances and parents should not be confused: zero-weight ties need a consistent update policy to avoid creating parent cycles during equal-value replacements.
Negative edges and Bellman–Ford
Proof
(Bellman–Ford computes distances and detects negative cycles)
Negative edges destroy Dijkstra's prefix inequality but can be handled by bounding the number of edges in a walk. Let be the minimum weight of a source walk to using at most edges, with and all other initial values infinite. Then
The alternatives are exhaustive: a walk either already has at most edges or has a last edge whose prefix has at most . Conversely each finite alternative appends an edge to an attainable walk. If no negative cycle is reachable from , removing cycles never increases a walk's cost, so an optimum can be chosen with at most edges. Therefore gives all distances.
The usual in-place Bellman–Ford initializes the distance array and makes passes relaxing every edge. After passes its values are no greater than , by induction using the fact that entries only decrease during a pass. They are still actual walk weights. Thus with no reachable negative cycle, after passes they equal the true distances. This gives time and auxiliary storage. A literal two-row evaluation of the displayed recurrence is equally correct but costs if each pass copies all vertices; its intermediate rows need not match in-place intermediate values.
An additional pass that can decrease a finite distance detects a reachable negative cycle. If there were none, all distances would already be exact, so no decrease could occur. Conversely, if no edge can decrease any value, summing the inequalities around a reachable cycle gives nonnegative total weight; all its vertices have finite labels after reachability has propagated. Hence a reachable negative cycle forces some further decrease. Unreachable negative cycles are not detected by a single-source initialization and do not affect that source's distances.
Worked examples
Worked example 3.2.7
(BFS layers on a directed graph)
Let edges be . BFS gives layers , , , , hence distances zero, one, two, three. Either or may become 's predecessor, depending on adjacency order. The distance is unique, while the selected shortest path need not be.
Worked example 3.2.8
(A spanning tree is not a shortest-path tree)
In an undirected triangle, let . The MST uses with total weight four. Its tree path from to has weight four, while the graph's shortest route is the single edge of weight three. A shortest-path tree rooted at uses , total weight five. Each tree optimizes its own stated objective.
Counterexample mode
No negative cycle is not enough for Dijkstra
Consider the claim that Dijkstra's finalization rule stays correct whenever the graph has no negative cycle. Take directed edges of weight two, of weight five and of weight negative four. Dijkstra finalizes with before it examines , because . The path has weight , so the true distance to is one. The graph has no cycle at all. The rule needs every individual edge weight to be nonnegative, and Bellman–Ford, which finalizes nothing early, finds the value one.
Worked example 3.2.9
(Dijkstra with an unreachable vertex)
Let the directed edges be of weight , of weight and of weight , and let have no incoming edge. Initially and the other labels are infinite. Finalizing and relaxing gives and . Finalizing , the smallest finite label, and relaxing gives . Finalizing with label leaves only , whose label is infinite, so the rule stops. The distances are . The direct edge to was not shortest, and the unreachable vertex keeps .
Concept lensStructural
Three selections, three certificates
BFS chooses the next queued vertex and certifies an edge-count layer. Kruskal chooses an edge and certifies extendability to a globally optimal spanning tree. Dijkstra chooses a smallest label and certifies that label cannot improve. These algorithms share a selection pattern, but their certificates and hypotheses differ; an MST exchange cannot replace a shortest-path finalization proof.
Common mistakes
Common mistake
(Check the problem before the algorithm)
Check whether the graph is directed, whether all vertices or one source matter, and whether weights may be negative. A disconnected undirected input has no spanning tree, although Kruskal produces a minimum spanning forest on its components. A DFS tree path is generally not shortest. Adding an edge to a partial spanning forest is safe because of the cut proof, not simply because the edge is inexpensive.
Common mistake
(Representation and sentinels)
Complexity depends on representation and data structures. Reading an adjacency matrix takes quadratic space, unlike a sparse adjacency list. A shortest-path algorithm must also distinguish infinity from a large finite number; the mathematical proofs do not justify a sentinel that can overflow or be mistaken for an actual distance.
Summary
Traversal invariants establish reachability, layers, and finish-time order. The MST cut exchange preserves extendability to an optimum. Dijkstra finalizes minimum labels using nonnegative weights, while Bellman–Ford replaces that hypothesis with repeated relaxation and explicit negative-cycle detection. Naming the protected certificate makes similar-looking graph procedures easier to distinguish and verify.
Exercises
Quick check
(Give a directed graph where DFS can first find a path longer than a shortest path, depending on adjacency order.)
Give both a direct edge to the target and a longer route.
Solution · Answer
Use edges , and explore before from . DFS first reaches along three edges, while the direct edge has length one. The discovery path is valid but not shortest.
Quick check
(Explain why replacing a cut-lightest edge by an arbitrary non-lightest crossing edge invalidates the MST exchange proof, and give a weighted triangle example.)
Which inequality does the swap use?
Solution · Answer
The exchange needs so that the swap does not increase the tree weight. Take a triangle with , , and the cut against . The edge crosses the cut but is not lightest, since crosses with weight one. Every spanning tree containing also contains or , so it weighs at least , whereas the minimum spanning tree weighs three. The edge is therefore not safe.
Quick check
(On edges of weight four, of weight five and of weight negative two, compute and the true distances.)
Write each row in the order .
Solution · Answer
In order , , and , because . No cycle exists, and the last row gives the true distances. An in-place pass that examines before may already produce two in its first pass, which is why its intermediate arrays need not equal the synchronous rows.
Exercise 3.2.10
(Prove that a finite directed graph has a topological ordering exactly when it has no directed cycle.)
CoreProof
Use the color argument for DFS proved above.
Solution(3)
- 1
An ordering rules out cycles
Along a directed cycle the positions of consecutive vertices would strictly increase and return to the starting vertex, which is impossible.
Because: In a topological ordering every edge strictly increases position.
- 2
Acyclicity rules out gray neighbors
Key step
If DFS on an acyclic graph met a gray neighbor from , the stack path from to together with the edge would be a directed cycle.
Because: A gray neighbor closes a cycle with the stack path.
- 3
Reverse finish order is topological
∎For an edge examined by DFS, is white and finishes before , or is already black and finished earlier. Hence finishes before , so precedes in reverse finish order. This holds for every edge, so the ordering is topological.