Data Structures and Algorithms: Dijkstra's Algorithm

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.

	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.