STEP-BY-STEP LESSON · §10.6
Spanning Trees and a Shortest Path Algorithm
Distinguish a minimum spanning tree from a shortest path.
Before you begin
Trees
A tree is a nonempty undirected graph that is connected and has no cycle. It has exactly one simple path between any two vertices, so deleting any edge disconnects it. A finite tree with n vertices has n−1 edges.
Weight and distance
An edge weight is the numerical cost of that edge. A route’s cost is the sum of traversed edge weights. A spanning tree’s total weight sums its selected edges. These are different objectives. Here ∞ marks a distance for which no route has yet been found.
Symbols
- w(T)
- total edge weight of a tree
- d(v)
- current distance estimate to v
- w(u,v)
- Weight of edge from u to v
- ∞
- No finite route found yet; every finite distance is smaller
Definitions and notation for this topic
Spanning tree
A spanning tree of a connected undirected graph uses every vertex of G and a subset of its edges, while remaining connected and without circuits.
A finite spanning tree has |V|−1 edges. A minimum spanning tree minimizes total edge weight among spanning trees; it need not minimize the route from one fixed source to every vertex.
Separate glossary example
In a triangle with edges AB=2, BC=3, AC=7, selecting AB and BC gives a spanning tree of total weight 5.
Weights, distance estimates and infinity
w(e); w(T); d(v); ∞
w(e) is the weight of a named edge; in a simple graph this may be written w(u,v). w(T) sums a tree’s edge weights. During a shortest-path algorithm d(v) may denote a tentative distance, and ∞ means no finite route has been found yet.
A tentative estimate is not automatically the final shortest distance. Dijkstra’s algorithm requires nonnegative edge weights. ∞ is an extended sentinel here, not an ordinary real weight.
Separate glossary example
If d(u)=4 and an edge e from u to v has weight 3, relaxation proposes d(v):=min(d(v),7). An old estimate ∞ becomes 7.
Step by step
Step 1 / 6
Define the objective
A spanning tree includes all vertices of a connected graph. A minimum spanning tree minimizes its total edge weight; a shortest path minimizes one route’s length.
Different objectives can select different edges.
Worked example
Triangle edges: AB=2, BC=2, AC=3. Compare an MST with the shortest A→C path.
- The tree AB,BC weighs 4; alternatives weigh 5.
- Within that tree, A→B→C has length 4.
- In the original graph, direct edge AC has length 3 and is shorter.
Build a spanning tree · interactive Prim example
Track why a tentative distance changes
For Dijkstra’s algorithm, weights must be nonnegative. d(v) is the best route length to v found so far; ∞ means no route has yet been found. A settled vertex has a final shortest distance. After settling u, test each unsettled neighbour v using d(u)+w(u,v), where w(u,v) is the edge weight. Keep the smaller distance and its predecessor.
Worked example
In an undirected graph, AB=4, AC=1, CB=2, BD=1, CD=5. Find the shortest distance and a shortest route from A to D using Dijkstra.
Initialize and settle A.
d(A)=0; d(B)=4; d(C)=1; d(D)=∞
Why: The empty route reaches A at cost 0. Its two edges provide the first routes to B and C.
Settle C, the unsettled vertex with the smallest tentative distance.
d(C)=1; d(B)=min(4,1+2)=3; d(D)=min(∞,1+5)=6
Why: The route A→C→B improves the previous direct route to B. A→C→D is the first known route to D, but is not yet final.
Settle B, then test its edge to D.
d(B)=3; d(D)=min(6,3+1)=4
Why: The earlier candidate of length 6 is replaced by A→C→B→D of length 4. Reaching a vertex once does not settle it.
Settle D and read the predecessor chain.
A→C→B→D; 1+2+1=4
Why: D now has the smallest unsettled distance. The predecessor chain records the route responsible for that distance.
Explain why selecting the smallest tentative distance is safe.
d(u)≤d(v)
Why: Assume distances already settled are correct. If a shorter route to the selected u existed, take the first unsettled vertex v along that route. Its predecessor is settled, so the edge to v has already been tested. Thus d(v) is at most that route’s prefix cost. Nonnegative remaining edges make the prefix no longer than the whole route. But selection gives d(u)≤d(v), contradicting that the whole route is shorter than d(u). The source at distance 0 starts this argument.
Try it yourself
In a different undirected graph, PQ=3, PR=8, QR=2, QS=7, RS=1. Start at P. Trace the distances to Q,R,S and explain why the first route found to S is not shortest.
Show worked answer
Settle P, then Q.
d(Q)=3; d(R): 8→min(8,3+2)=5; d(S)=3+7=10
Why: Q is selected before R because 3<8. Through Q, the route to R improves and the first route to S is found.
Settle R and update S, then settle S.
d(S): 10→min(10,5+1)=6; P→Q→R→S
Why: The route through R improves S to 6. Earlier discovery at 10 did not make that distance final.
Optional self-check
Triangle weights are AB=1, BC=1, AC=1.5. Does an MST necessarily contain the shortest A–C route?
Show answer
No. The MST uses AB,BC for total 2; its A–C route has length 2. The original graph has the shorter direct edge AC of weight 1.5.