A graph can support several different questions. Which vertices are reachable? How many edges does a shortest route use? What is the least total edge weight of a route? Which edges connect the whole network as cheaply as possible? Similar drawings do not make these questions interchangeable. Their algorithms are best understood by attaching an exact meaning to each frontier, distance label and selected edge.
Motivation
Imagine vertices as locations and edges as permitted moves. When every move has the same cost, processing vertices in order of their discovery naturally reveals increasing route lengths. When costs differ, discovery order is no longer enough: an expensive one-edge route can lose to a cheap multi-edge route. A priority rule must track tentative total costs instead.
A spanning-tree problem changes the objective again. It pays for a collection of edges once, so all vertices become connected. It does not minimize each traveler's distance from a selected source. A network that is cheapest to build may force a longer journey between some of its vertices. Explaining that distinction prevents a common misuse of shortest-path algorithms as minimum-spanning-tree algorithms.
All three problems admit a useful frontier view. BFS separates processed layers from undiscovered vertices. Dijkstra separates vertices whose distances are final from those with tentative labels. A spanning-tree algorithm separates connected components or a growing tree from the rest. What differs is the proof that crossing the frontier in the proposed way is safe.
Definitions
Definition 4.5.1
(Walks, paths and reachability)
A finite directed graph has a vertex set and directed edges . An undirected edge joins two vertices without a direction; for traversal it can be represented by two directed incidences. A walk follows consecutive edges and may repeat vertices. A path will mean a walk without repeated vertices. A vertex is reachable from if some walk leads from to it; deleting repeated closed sub-walks produces a path when reachability holds.
Definition 4.5.2
(Unweighted distance and BFS)
In an unweighted graph, the distance is the minimum number of edges in a walk from to , or infinity if no such walk exists. BFS uses a first-in-first-out queue. It sets , marks discovered, and repeatedly removes the front vertex . Every as-yet undiscovered neighbor is marked immediately, assigned and parent , and added to the back of the queue.
Definition 4.5.3
(Weighted distance and Dijkstra's algorithm)
For a weighted graph, a walk's weight is the sum of its edge weights. Dijkstra's algorithm assumes every edge weight is nonnegative. It initializes and other labels to infinity. Repeatedly it selects an unsettled vertex of minimum finite label, settles it, and relaxes its outgoing edges: if , replace the latter label and record parent . Stop when no finite unsettled label remains. The weighted distance is the least weight of a walk from to , or infinity if there is none.
Definition 4.5.4
(Spanning trees, minimum spanning trees and cuts)
For a connected undirected graph, a spanning tree is a connected acyclic subgraph containing every vertex. It has edges. A minimum spanning tree, or MST, minimizes the sum of its edge weights. Edge weights for an MST may be negative: unlike shortest walks, a tree cannot traverse a negative cycle repeatedly. A cut of the graph is a partition of its vertices into two nonempty parts. An edge crosses the cut if its endpoints lie in different parts, and an edge set respects the cut if none of its edges crosses it.
Theorem/proposition
Theorem 4.5.5
(BFS computes unweighted distances)
In a finite graph represented by adjacency lists, BFS discovers exactly the vertices reachable from its source and assigns each its minimum edge-count distance. Each vertex is enqueued at most once, and the running time is including initialization.
Theorem 4.5.6
(Dijkstra's settled labels are final)
For a finite directed or undirected graph with nonnegative edge weights, each vertex settled by Dijkstra satisfies for weighted distance. A vertex left at infinity is unreachable when the algorithm terminates.
Theorem 4.5.7
(Cut property for minimum spanning trees)
Let be a connected finite undirected weighted graph and let be an edge set contained in some MST. Fix a cut, meaning a partition of the vertices into two nonempty parts, crossed by no edge of . If is a minimum-weight edge crossing the cut, some MST contains . In particular a lightest crossing edge belongs to some MST, although ties need not force it into every MST.
In the safe-edge statement, “previous choices” are assumed to be contained in at least one MST, and the cut must respect them, meaning none crosses it. Stating that invariant is essential when using the cut property repeatedly in an algorithm.
Proof sketch or proof idea
Proof
(BFS labels equal distances)
BFS queue labels are nondecreasing from front to back: processing a label- vertex can append only label- vertices, after all currently queued label- vertices. Every assigned label is realized by its parent chain, so it cannot be smaller than the true distance. Conversely, take a vertex of true distance and a shortest path to it. Its predecessor has distance and, by induction on , is processed with that correct label. The vertex is either already discovered with a label at most , or is then discovered with label . Combined with the realized-path inequality this gives equality. Reachable vertices occur at some finite path length, so induction discovers all of them; no unreachable vertex can receive a parent chain from .
Proof
(A selected label is already exact)
For Dijkstra, every finite label is the weight of an actual source walk, so . Assume all previously settled labels are correct and let be the next selected vertex. On a shortest path to , let be the first unsettled vertex, with preceding vertex settled, unless in the initial step. Relaxing the edge from gave , so equality holds. Nonnegative remaining edges give . Minimality of the selected label yields
Thus all inequalities are equalities and is settled correctly. The source starts the induction. A shortest path exists for every reachable vertex: with nonnegative weights, removing cycles cannot increase weight, so a minimum can be taken over finitely many simple paths. If a reachable vertex remained at infinity, a first undiscovered vertex on a path would have received a finite relaxation from its settled predecessor, contradicting termination.
Proof X-ray
Where nonnegativity enters
Two inequalities pin down a settled label. The easy one, , holds because a finite label is the weight of a real walk. The hard one, , comes from the first unsettled vertex on a shortest path to . Choosing the first one makes everything before it settled, so was relaxed from a correct label and ; and had the minimum label among unsettled vertices, so . Nonnegativity enters at exactly one link of the chain, , where the rest of the path from to must not have negative weight. In the negative-edge counterexample below, is selected first, the first unsettled vertex on its shortest path is , and that link fails: .
Proof
(Exchange a heavier crossing edge for the lightest one)
For the cut property, start with an MST containing the previous choices. If it contains the proposed crossing edge , there is nothing to do. Otherwise adding produces one cycle: the original tree already has a unique path between its endpoints. That path crosses the cut, so the cycle contains another crossing edge . Because the cut respects all previous choices, is not one of them. Remove . The result is a spanning tree retaining the previous choices and containing . Since was a lightest crossing edge, , so the new tree's weight is no larger. Minimality makes it an MST. This is an exchange argument, with feasibility ensured by the cycle replacement.
Prim's algorithm starts at one vertex and repeatedly takes a minimum-weight edge from its growing vertex set to the outside. Its cut respects all previously selected edges, so the cut property preserves the invariant that the selected forest extends to an MST. Kruskal's algorithm processes edges by increasing weight and adds an edge only when its endpoints belong to different current components. For an added edge, the cut separating one of those components from the rest is respected, and no lighter crossing edge can have been rejected between different components. The same invariant proves correctness. Each successful addition reduces the number of components, so connected input leads to a spanning tree.
Worked examples
Worked example 4.5.8
(Distances by edge count and by weight)
Use the undirected graph with edges , , , , , , , . BFS from assigns distances zero to , one to , and two to . Dijkstra instead settles in the order with weighted distances . The cheapest route to is , using four edges. A two-edge route exists but has weight eleven, so BFS's correct answer for its objective is not a weighted shortest route.
Worked example 4.5.9
(A shortest-path tree need not be an MST)
Take three vertices with weights , , . A shortest-path tree rooted at uses both source edges and has total edge weight four. An MST uses and either source edge, of total weight three. In that MST, one source-to-vertex distance becomes three rather than the optimum two. Minimizing construction cost and minimizing source distances make different demands on the same graph.
Worked example 4.5.10
(Kruskal on the weighted graph, with rejected edges)
On the graph of the first example, sort the edges: , , , , , , , . Take : it joins the components and . Take : it joins and ; the two weight-one edges are disjoint, so either order gives the same result. Take : it joins to . The cut separating from the rest is crossed by , , and , and is the lightest, as the cut property requires. Take : it joins to the rest, and the forest now has edges with total weight . The remaining edges , , and each have both endpoints in the single component and would close a cycle, so Kruskal rejects them. The rejections are the boundary case: an edge is discarded when its endpoints are already connected, whatever its weight.
Counterexample mode
A negative edge defeats permanent settling
A plausible claim is that Dijkstra's rule gives correct distances whenever the graph has no negative cycle. Take the directed graph with of weight two, of weight five and of weight minus four. It has no cycle at all. The labels after the first relaxation are and , so Dijkstra settles with label two. It then settles ; relaxing would give , but is already settled. The walk has weight one, so . The repair is to require nonnegative weights for the settling rule. With negative edges one needs a procedure that may revisit settled labels, which is no longer the algorithm proved above.
With adjacency lists, BFS scans each directed edge once, or each undirected incidence twice, and each vertex once. A simple array implementation of Dijkstra finds each minimum by scanning all vertices, giving operations. A binary heap with an appropriate decrease-key implementation gives operations for nontrivial graphs. Kruskal requires sorting the edges and maintaining components; even a simple component implementation is polynomial, while disjoint-set structures improve the component operations. These costs assume constant-cost comparisons and arithmetic on edge weights. Exact rational weights with long encodings require a separate bit-cost analysis.
Common mistakes
Common mistake
(Marking BFS vertices only when they are removed)
Mark BFS vertices when enqueuing, not only when removing them, if the one-enqueue invariant is being used. Otherwise several neighbors can enqueue the same vertex before it is processed. The resulting procedure may still be repairable, but its state and cost proof have changed.
Common mistake
(Applying the cut proof to a disconnected or directed graph)
For disconnected input, an MST of all vertices does not exist; the natural analogue is a minimum spanning forest, one tree per component. A directed minimum-cost connection problem is also different from the undirected MST problem. Do not silently apply the cut proof where directed reachability replaces undirected connectivity.
Common mistake
(Expecting a lightest edge to lie in every MST)
Equal weights can produce several MSTs. The cut property promises existence of one containing a chosen lightest edge, not universal membership when tied alternatives exist. In a triangle whose three edges all have weight one, every pair of edges is an MST, so each edge is left out by one of them. If a cut has a unique lightest edge, the exchange proof strengthens to show it belongs to every MST.
Summary
BFS uses layers because every edge contributes one unit. Dijkstra uses tentative weights and needs nonnegative edges to finalize a frontier minimum. MST algorithms minimize a global edge-set cost and use cut-and-cycle exchanges. The data structures implement these ideas; the invariants explain why the resulting answers solve the stated problems.
Exercises
Quick check
(Find an MST of the five-vertex graph in the worked example on distances by edge count and by weight, and give its total weight.)
Sort the edges and skip any that would close a cycle.
Solution · Answer
Select of weight one, of weight one, of weight two and of weight three. These connect all five vertices without a cycle and have total weight seven. The cut property, applied at each step as in the Kruskal worked example, certifies minimality. The four selected edges also happen to form the weighted shortest-path tree from in this example, but the second worked example shows this coincidence is not general.
Exercise 4.5.11
(Prove that a unique lightest edge across a cut belongs to every MST.)
CoreProof
Let be a connected weighted undirected graph, and let be the only minimum-weight edge crossing a fixed cut.
Solution(3)
- 1
Assume an MST omits
is a spanning tree, so it has a unique path between the endpoints of . Adding to creates exactly one cycle.
- 2
Find a second crossing edge on that cycle
Key step
The cycle uses , which crosses the cut, so it contains another crossing edge . Because is the unique lightest crossing edge, .
Because: A cycle crosses a cut an even number of times.
- 3
Swap the edges and contradict minimality
∎Removing an edge of the unique cycle leaves a spanning tree, so is one, with . This contradicts the minimality of , so every MST contains . The strict inequality is exactly the extra fact unavailable when weights tie.
Quick check
(Explain why BFS is valid on a graph whose edges all have the same positive weight, and how to obtain weighted distances from its output.)
Compare the weight of a walk with its number of edges.
Solution · Answer
If every edge has weight , a walk with edges has weight , so minimizing weight is the same as minimizing the number of edges. Multiply each finite BFS distance by ; unreachable vertices remain at infinity. The case is trivial: every reachable weighted distance is zero.
Quick check
(In the negative-edge example, compute the correct distances and identify exactly which step of the Dijkstra induction fails.)
Look for the first unsettled vertex on the true shortest path to .
Solution · Answer
The distances are zero to , five to , and one to . When is chosen before , the first unsettled vertex on the true shortest path to is , whose distance five is greater than the final path cost one. Thus the suffix inequality fails, because the last edge of that path has negative weight.