Dijkstra’s Shortest Path

The cheapest way from one place to every other place when roads have different lengths.

The idea (a GPS)

BFS finds the path with the fewest roads, but real roads have different lengths. Dijkstra finds the path with the smallest total length. It keeps a notebook of the best known distance to every place, starting with ∞ (unknown) everywhere except the start (0).

  1. Pick the unfinished place with the smallest known distance. Nothing can beat it, because every other route to it would have to pass through a place that is already farther away. So its distance is final.
  2. From it, try each road: is distance so far + road length smaller than what we have written for the neighbor? If yes, relax the edge: update the notebook.
  3. Repeat until nothing is left.

The “pick the smallest” step is a priority queue (a min-heap, see the heap page). It requires every road length to be positive.

Watch it work

Roads work in both directions. Nodes are numbered 0, 1, 2, ... with no gaps (at most 10 nodes, 15 roads). Lengths are whole numbers from 1 to 99.

Try it

Common mistakes

Complexity, in plain English: each road may add one entry to the priority queue, and each queue operation costs about log(entries). So the time is about O((V + E) log V). It is fast even on big maps, but it still needs memory for the distances and the queue.