Edges now have lengths, such as kilometres, minutes or costs. The length of a path is the sum of its edges, and we want the shortest distance from a start node to every other node. BFS isn't enough: it finds the path with the fewest edges, but three short edges can beat one long one.
Every node gets a tentative distance: the shortest path to it found so far (∞ at first; 0 for the start). Repeat:
Why is the closest node safe to settle? Any other route to it would have to leave the settled region through some other unsettled node. That node is already at least as far away, and edges never have negative length, so the detour can't be shorter.
A distance ∞ B tentative distance, waiting in the queue C just settled D settled: distance is final
Numbers under the nodes are their current distances. Ties are broken alphabetically, and a distance is only updated when the new path is strictly shorter, so each question has one right answer.
"Pick the closest unsettled node" is exactly what a min-priority queue does. With a binary heap (a min-heap: the mirror image of the max-heap), picking costs O(log V) and so does lowering a distance.
| Dijkstra | |
|---|---|
| Time | O((V + E) log V) with a binary heap |
| Works when | No edge has negative length. With negative edges, use Bellman–Ford. |
| All edges length 1? | Then it settles nodes in the same rings as BFS. |