Chapter 9 · Greedy Technique
Prim, Kruskal & Dijkstra
Three greedy algorithms on the same weighted graph. Prim and Kruskal build a Minimum Spanning Tree (MST) — the cheapest set of edges that connects everything. Dijkstra builds a Shortest-Path Tree (SPT) from one source. Each step grabs the locally best option and never takes it back.
Edit mode: click empty space to add a vertex; click a vertex, then another, to add that edge (or remove it if it exists).
predictions: 0 / 0
🤔 Predict:
tree vertex
fringe vertex (has a finite label)
vertex / edge being examined
tree edge
cycle that would form / other algorithm's pick
rejected edge
Labels
Priority queue
MST vs shortest-path tree on this graph
How to read this
- Labels under vertices follow Levitin's notation. Prim:
b(a, 3)= the nearest tree vertex is a, by an edge of weight 3. Dijkstra:b(a, 3)= best path found so far arrives from a and has total length 3.(−, ∞)means “not reachable yet”. - The Tree vertices / Remaining vertices table grows one row per step, just like the textbook's trace tables. Red entries were just updated.
- The priority queue lists fringe vertices by key; the greedy step always removes the top one.
- Kruskal scans edges from lightest to heaviest. The union-find forest shows which vertices are already connected: two vertices with the same root are in the same tree, so an edge between them would close a cycle (drawn in purple) and is rejected.
- At the end, dashed purple edges belong to the other tree (MST vs SPT) — handy for the “Prim vs Dijkstra” preset.
Try this
- Run Prim on the Levitin §9.1 graph from a. The picks should be b(a,3), c(b,1), f(b,4), e(f,2), d(f,5): total weight 15.
- Switch to Kruskal on the same graph. It accepts bc 1, ef 2, ab 3, bf 4, then rejects cf 4 (b and c are already joined through the tree) and af 5, and finishes with df 5. Same total, 15.
- Pick the Levitin §9.3 graph and Dijkstra from a: b(a,3), d(b,5), c(b,7), e(d,9). Check each path length yourself.
- Load “⚖️ Prim vs Dijkstra differ here”. Prim takes b–c (weight 2), Dijkstra takes a–c (weight 5). Why is each right for its own goal?
- Turn on 🤔 Predict and call every greedy choice before it happens. Then edit a weight so the answer changes and try again.