Objective
Compute shortest paths from a source and watch Dijkstra's algorithm settle nodes one by one in order of distance.
The idea
Dijkstra's algorithm is the classic single-source shortest path. Watch it expand to the nearest unsettled node, relaxing edges as it goes.
Try this
- 1Run it and watch nodes settle in distance order.
- 2Add a heavy edge and see it avoided.
- 3Add a negative edge and watch the algorithm break.
- 4Read the final distances and the shortest-path tree.
Watch for
- Each iteration settles the nearest unsettled node.
- Relaxation may improve a neighbour's tentative distance.
- The settled set grows like a wave from the source.
- Negative edges break the greedy guarantee.