Shortest Paths: Dijkstra

Dijkstra finds the shortest distance from one source node to every other node in a weighted graph, as long as all edge weights are non-negative.

Core terms

• Single-source shortest paths: cheapest total cost from one source to all other nodes at once.
• Weighted edge: an edge carrying a cost/weight; a path length is the sum of its edge weights.
• Relaxing edge u -> v with weight w: if dist[u] + w < dist[v], update dist[v] = dist[u] + w.
• Finalize: lock in a node’s distance as the true shortest; it never changes again.

The algorithm

Init dist[source] = 0, all others INF; heap starts as [(0, source)]. Repeat:

1. Pop the smallest-distance unfinalized node from the min-heap.
2. If its popped distance > dist[u], it is stale; skip.
3. Otherwise finalize it and relax all outgoing edges, pushing improved neighbors.

init dist=INF (source=0), heap=[(0,src)]
      |
      v
  pop smallest (d,u)  <-------+
      |                       |
   d > dist[u]? --yes--> skip |
      | no                    |
  relax edges of u,           |
  push improved neighbors ----+
      |
   heap empty -> done

Key facts

• Nodes leave the heap in non-decreasing distance order; that ordering makes “finalize the closest” safe.
• Correctness relies on non-negative weights: extra edges can only add cost, so the closest unfinalized node cannot be improved later.
• Store heap pairs as (distance, node) so tuples compare by distance first. Node-first would sort by name, which is wrong.
• Unreachable nodes keep dist = INF; that is correct, not a bug.
• Undirected roads need both A -> B and B -> A in the adjacency list.

Complexity

Gotchas

• Stale entries: cheaper routes push new pairs without removing old ones; the if d > dist[u]: continue guard skips them. Omitting it wastes work.
• Negative edges break it: e.g. A->B=2, A->C=5, C->B=-4 gives true B=1 but Dijkstra locks B=2. Use Bellman-Ford instead.
• Dijkstra never revisits a finalized node, so a wrong lock-in is permanent.