Dijkstra's Algorithm: Settling the Closest Vertex Next

Dijkstra's algorithm finds the shortest path from one source to every vertex of a graph whose weights are not negative. It repeatedly picks the vertex with the smallest distance that is not yet final, makes it final, and relaxes the edges out of it. This card traces it on the topic's graph from A and keeps its four parts apart, because confusing them is the usual way a trace goes wrong.

The four parts are: the distances, the best length found yet for each vertex; the settled set, the vertices whose distance is final; the parents, which rebuild the paths; and a priority queue, a structure that hands back its smallest entry first, holding (distance, vertex) pairs for vertices not yet settled. A vertex is settled when it leaves the queue with its smallest distance. The queue is not the paths and not the settled set: it is only a way to find the next vertex to settle.

When a distance is lowered, the new pair goes into the queue and the old one stays there, stale, until it surfaces and is skipped. The steps below are from a run, one per vertex settled.

queue: (2,B) (7,C)

queue: (5,C) (7,C) (10,D)

queue: (7,C) (7,D) (10,D) (11,E)

queue: (8,E) (10,D) (11,E)

queue: (10,D) (11,E)

Each vertex's distance was lowered more than once before it settled: C from 7 to 5, D from 10 to 7, and E from 11 to 8. Settling is what makes a distance final, and the queue's order is what makes settling safe. When a vertex leaves the queue with the smallest distance of all the unsettled ones, any other route to it would have to leave the settled set through a vertex at least as far away and then add edges. With no negative weights, adding edges never makes a path shorter, so no such route can beat it.

The same argument marks the algorithm's limit: with one negative edge, a route that arrives later can be shorter, which Running Dijkstra's Algorithm on a Negative Edge shows. Dijkstra's algorithm is greedy in the sense of Greedy Algorithms: it commits to the closest vertex and never revisits it.

Water poured in at A fills the nearest pools first and reaches E last, along the cheapest channels. The picture breaks because water spreads along every channel at once, while the algorithm settles exactly one vertex at a time.

Reach for Dijkstra's algorithm when a problem asks for the cheapest, fastest or shortest route from one place, and every cost is 0 or more: road distances, travel times, network delays.