Data Structures and Algorithms 
Operation of Dijkstra's Algorithm 
This sequence of diagrams illustrates the operation of Dijkstra's Algorithm.
Initial graph 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 