|Data Structures and Algorithms|
|Operation of Dijkstra's Algorithm|
This sequence of diagrams illustrates the operation of Dijkstra's Algorithm.
All nodes have infinite cost except the source
|Choose the closest node to s.
As we initialised d[s] to 0, it's s.
Add it to S
Relax all nodes adjacent to s.
Update predecessor (red arrows) for all nodes updated.
|Choose the closest node, x
Relax all nodes adjacent to x
Update predecessors for u, v and y.
|Now y is the closest,
add it to S.
Relax v and adjust its predecessor.
|u is now closest, choose it and adjust its neighbour, v.|
|Finally, add v.
The predecessor list now defines the shortest path from each node to s.
|Back to Dijkstra's Algorithm||Back to the Table of Contents|