Dijkstra's algorithm

How Dijkstra's algorithm works

Step by step

1. All distances start at infinity except A at 0. The queue holds one entry, (0, A); nothing is settled.
2. Settle A. Relaxing its edges writes dist[B] = 4 and dist[D] = 2, and pushes both nodes onto the queue.
3. D is the cheapest entry at 2 - settle it. Its edges relax E to 2 + 5 = 7 and G to 2 + 7 = 9.
4. Settle B at 4. It offers E a route of 4 + 3 = 7 - a tie with the existing 7, not an improvement, so nothing is written.
5. Settle E at 7, relaxing F to 11 and H to 10. Then G settles at 9; its offer to H, 9 + 1 = 10, ties and is ignored.
6. C settles at 10 and offers F 10 + 2 = 12 - worse than 11, rejected. H and then F settle, and the queue empties.
7. Final distances from A: B 4, C 10, D 2, E 7, F 11, G 9, H 10. The relaxations that survived form the shortest-path tree.

Complexity

Reference implementation

import heapq

def dijkstra(adj, start):
    dist = {u: float("inf") for u in adj}
    dist[start] = 0
    prev = {}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                    # stale entry, already improved
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:            # relax
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, prev

function dijkstra(adj, start) {
  const dist = new Map([...adj.keys()].map((u) => [u, Infinity]));
  dist.set(start, 0);
  const prev = new Map();
  // A real implementation uses a binary heap; a sorted array is
  // clearer and fine for small graphs.
  const pq = [[0, start]];
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();
    if (d > dist.get(u)) continue;
    for (const { to: v, w } of adj.get(u) ?? []) {
      const nd = d + w;
      if (nd < dist.get(v)) {
        dist.set(v, nd);
        prev.set(v, u);
        pq.push([nd, v]);
      }
    }
  }
  return { dist, prev };
}

static Map<String,Integer> dijkstra(Map<String,Map<String,Integer>> adj, String start) {
    Map<String,Integer> dist = new HashMap<>();
    PriorityQueue<Object[]> pq =
        new PriorityQueue<>(Comparator.comparingInt(a -> (int) a[0]));
    dist.put(start, 0);
    pq.add(new Object[]{0, start});
    while (!pq.isEmpty()) {
        Object[] top = pq.poll();
        int d = (int) top[0];
        String u = (String) top[1];
        if (d > dist.getOrDefault(u, Integer.MAX_VALUE)) continue;
        for (Map.Entry<String,Integer> e : adj.getOrDefault(u, Map.of()).entrySet()) {
            int nd = d + e.getValue();                 // relax u -> v
            if (nd < dist.getOrDefault(e.getKey(), Integer.MAX_VALUE)) {
                dist.put(e.getKey(), nd);
                pq.add(new Object[]{nd, e.getKey()});
            }
        }
    }
    return dist;
}

Common pitfalls

• Running it with negative edge weights. The greedy proof assumes extending a path never shortens it; one negative edge and a settled node can be wrong. Use Bellman-Ford instead.
• Skipping the stale-entry check. Pushing duplicates is fine, but each pop must be ignored when its distance exceeds dist[u], or you reprocess nodes with outdated values.
• Settling a node at push time instead of pop time. A node can be discovered via an expensive route first; committing early locks in the wrong distance.
• Using it for longest paths by negating weights. Negation creates negative edges, which is precisely the input Dijkstra cannot handle.
• Forgetting the predecessor map. Distances alone cannot reproduce the route - record prev[v] = u at each successful relaxation and walk it backwards.

Where it is used

• Road navigation - GPS routing is Dijkstra at heart, usually accelerated with heuristics and preprocessing.
• Link-state network routing: OSPF has each router run Dijkstra over the topology it has learned.
• Interview staples like Network Delay Time and Path With Minimum Effort, both direct applications.
• The base of A* - add an admissible heuristic to Dijkstra and you get goal-directed search.

Frequently asked questions