Dijkstra's algorithm finds shortest distances from a source to other vertices. Repeatedly finalize the unsettled node with the smallest tentative distance, then improve neighbors' distances through it.

A weighted-graph simulator showing finalized nodes and distance relaxations

1. Click a source node (currently A)

2. Step through the transfer

UnsettledNewly finalizedFinalizedEdges checked this stepShortest-path treePath to selected node

Yellow table cells mark distances improved in this step. After the run, click a node to highlight its shortest path from the source.

Why finalize the closest node first?

Let u be the unsettled node with the smallest tentative distance. Any alternative path through another unsettled node already costs at least that much. With nonnegative edge weights, extending it cannot make it cheaper. This argument fails for negative edges; use an algorithm such as Bellman–Ford in that case.

Burst time

A heap-based priority queue gives O((V + E) log V) time. Dijkstra's algorithm underlies routing and shortest-path applications, including OSPF.