A map app finds the fastest route among millions of roads in an instant. The core idea is Dijkstra's algorithm, which grows a set of vertices whose distances are known for sure. Like Kruskal's algorithm, it makes one greedy choice per round, but a different one.
Key idea
Dijkstra's algorithm (weights $\ge 0$): give the start distance $0$ and every other vertex $\infty$. Each round, settle the unsettled vertex with the smallest tentative distance; then, for each neighbor, if going through the settled vertex is shorter, lower that neighbor's tentative distance. A vertex's distance is final only when it is settled.
Why it works
Why is the closest unsettled vertex $u$ safe to settle? Any other route from the start to $u$ must leave the settled set at some point, through an edge to some unsettled vertex $w$. Reaching $w$ already costs at least its tentative distance, which is at least $u$'s (that is how $u$ was chosen), and the rest of the route adds weights that are $\ge 0$. So no route beats $u$'s current distance. This is also why negative weights break the algorithm: a later negative edge could make a detour cheaper.
Worked examples
Worked example: A full run
In the graph above, find the shortest distance from $A$ to every vertex.
- Settle $A$ ($0$). Update: $B = 4$, $C = 2$.
- Settle $C$ ($2$, the smallest). Update: $B = \min(4, 2 + 1) = 3$; $E = 2 + 8 = 10$.
- Settle $B$ ($3$). Update: $D = 3 + 5 = 8$; $E$ stays $10$ ($3 + 10 = 13$ is worse).
- Settle $D$ ($8$). Update: $E = \min(10, 8 + 2) = 10$ (a tie), $F = 8 + 6 = 14$.
- Settle $E$ ($10$). Update: $F = \min(14, 10 + 3) = 13$. Settle $F$ ($13$).
Answer: $A\,0$, $C\,2$, $B\,3$, $D\,8$, $E\,10$, $F\,13$
Worked example: The first route found is not always the best
In the run above, $B$ was first reached with distance $4$. Why wasn't $B$ settled then?
- When $B$ got its tentative $4$ from $A$, $C$ was closer ($2$).
- Settling $C$ first revealed the route $A \to C \to B$ of length $3$.
- Settling only the closest vertex each round is what guarantees each settled distance is final.
Answer: $A \to C \to B$ was shorter.
Common mistake
Settling a vertex as soon as it is reached. If $B$ had been fixed at $4$, every distance computed through $B$ would be off too. Check: each round, compare all unsettled tentative distances and settle only the smallest; until then, a distance is just the best found so far.