The Cheapest Way to Connect Every City
Suppose you must connect several cities with cables. Each cable costs a different amount, and the budget is tight. To keep every city connected with no gaps while minimizing total cable cost, which cables should you lay?
A tree that "connects all nodes with no cycle, at minimum cost" is called a Minimum Spanning Tree (MST). If there are \(V\) nodes, exactly \(V-1\) edges connect them all.
Example: if the MST connecting 6 cities A·B·C·D·E·F has total cost 19, the goal is to pick the 5 edges that produce that 19.
Two classic algorithms find an MST: Kruskal, which sorts all edges and scans from cheapest, and Prim, which we'll look at today.
How Does Prim Approach It? (The Core Idea)
While Kruskal "sorts all edges and takes the cheapest", Prim works differently.
Start from one node and grow the tree by repeatedly adding the "cheapest edge that attaches to the tree built so far".
1. Put one starting node into the tree
2. Find the cheapest edge that can attach to the tree
3. Use it to absorb one new node into the tree
4. Repeat steps 2-3 until all nodes are in
Like rolling a snowball, the single blob that is the tree grows one node at a time, always in the cheapest direction.
Why Pick 'Edges' with a Priority Queue?
A natural question arises: how do we quickly find "the cheapest edge that can attach to the tree" every single time?
As the tree grows, the candidate edges crossing its frontier keep appearing and disappearing. Scanning all of them each time is slow. So we push (edge cost, the node that edge reaches) into a priority queue (min-heap), so that popping always yields the cheapest one first. Each time we absorb a new node, we push its neighbor edges into the queue — so the queue always holds the "current attach candidates" in sorted order.
For each node we remember key[v] = "the cheapest edge cost connecting v to the current tree", and lower it whenever a cheaper edge appears. That "lower it when cheaper" step is exactly relaxation.
Isn't This Just Dijkstra?
The code really does look alike. Both pop (value, node) from a priority queue and relax neighbors. But the 'value' you pop and compare is different.
| Dijkstra | Prim | |
|---|---|---|
| Value in the queue | accumulated distance from the source | cost of a single edge attaching one node |
| Relaxation | dist[u] + w (path sum) | w (one edge) |
| What it finds | shortest path from a source | minimum tree connecting everything |
Dijkstra weighs the sum of "how far we've come from the source", while Prim only looks at "the single edge that attaches this node to the tree". This one subtle difference splits the result entirely into shortest path vs minimum spanning tree.
It Clicks When You See It
In words, "distance sum vs single edge" is easy to confuse. But once you watch the tree grow node by node and the priority queue spit out the cheapest edge, it clicks instantly.
On AlgoNote you can follow Prim growing the tree from a start node on a 6-node graph, step by step — including key updates and how the priority queue changes. See which edges get chosen, which get discarded (already inside the tree), and exactly how the final MST cost comes out to 19.