Dijkstra's Shortest Path

Dijkstra's algorithm finds the cheapest route from one node to every other node in a graph whose edges have non-negative costs, by always settling the closest node it has not settled yet.

Start at A

4215810262
A0
B∞
C∞
D∞
E∞
F∞

Distances

A0
B∞
C∞
D∞
E∞
F∞

Visit order: —

  • Current
  • Reached, not settled
  • Settled
  • Edge being checked

Every distance starts at ∞, except A at 0. Dijkstra always settles the closest unsettled node next.

Step 1 / 26
Settled
0
dist[start] = 0; every other dist = ∞
while some node is unsettled:
  node = unsettled node with the smallest dist
  settle node
  for each neighbour: if dist[node] + w < dist[nb]:
    dist[nb] = dist[node] + w; prev[nb] = node
Start atRoute to(shown at the end)

What's happening?

  1. Every distance starts at infinity, except the start at 0.
  2. Settle the unsettled node with the smallest distance — no other route to it can be shorter.
  3. For each of its neighbours, check whether going through it is cheaper than the best route known so far; if so, update.

Complexity

Time
O((V + E) log V) with a priority queue
Space
O(V)

Where you'll meet it

Maps and navigation, network routing (OSPF), game path-finding (A* is Dijkstra with a hint), and cheapest-flight style searches.

Common mistake

Using it with negative edge weights. "Closest first" is only safe when costs never go down — use Bellman-Ford instead.

FAQ

Why can a settled node never change?

Every other route would have to pass through an unsettled node that is already at least as far, and weights cannot be negative.

What is the priority queue for?

Finding the closest unsettled node quickly instead of scanning all of them each time.

Dijkstra vs BFS?

BFS counts edges; Dijkstra adds up their costs. With all costs equal they give the same answer.