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
© , 1998