Dijkstra's Algorithm

Description

BFS finds the path with the fewest edges. Once edges have weights, such as road lengths, latencies or prices, the fewest edges is no longer the cheapest route. Dijkstra's algorithm finds the cheapest distance from one source to every node. It settles nodes in order of distance, always expanding the closest unsettled one next from a min-heap. It's correct as long as no edge weight is negative.

We'll go from simple to more technical:

1. The pattern: a min-heap of (distance, node) with lazy deletion of stale entries.
2. A second flavor: other path costs, such as the worst single step instead of the sum.
3. Where it runs in production (routing, network paths, maps).
4. What breaks it: negative edges, stale entries, and comparators.

The approach

int[] dijkstra(int n, List<List<int[]>> adj, int src) {         // adj.get(u) holds {v, weight}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));   // {node, dist}
    pq.add(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int node = cur[0], d = cur[1];
        if (d > dist[node]) continue;                              // stale entry - a shorter one was already used
        for (int[] edge : adj.get(node)) {
            int next = edge[0], weight = edge[1];
            if (dist[node] + weight < dist[next]) {
                dist[next] = dist[node] + weight;
                pq.add(new int[]{next, dist[next]});
            }
        }
    }
    return dist;
}

import heapq


def dijkstra(n: int, adj: list[list[tuple[int, int]]], src: int) -> list[float]:   # adj[u] holds (v, weight)
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]                          # (dist, node): tuples compare by their first item
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                           # stale entry - a shorter one was already used
        for nxt, weight in adj[node]:
            if d + weight < dist[nxt]:
                dist[nxt] = d + weight
                heapq.heappush(heap, (dist[nxt], nxt))
    return dist

The heap always hands back the unsettled node with the smallest known distance. With non-negative weights, no path discovered later can be shorter - every other route leaves through a node that is at least as far away, and edges only add. So that node's distance is final, and relaxing its edges is safe. Java's PriorityQueue can't lower an existing entry's key, so the code simply pushes a new entry on every improvement and skips any popped entry that's out of date - "lazy deletion". Python's heapq has no decrease-key either, so the Python version works the same way.

A second flavor: other path costs

The argument never used the fact that path costs are sums - only that extending a path never makes it cheaper. "Effort" on a hiking grid - the largest height difference of any single step - has the same property, so the same algorithm works with max in place of +:

int next = Math.max(effort, Math.abs(heights[nr][nc] - heights[r][c]));   // cost of a path = its worst step
if (next < best[nr][nc]) { best[nr][nc] = next; pq.add(new int[]{next, nr, nc}); }

step = max(effort, abs(heights[nr][nc] - heights[r][c]))   # cost of a path = its worst step
if step < best[nr][nc]:
    best[nr][nc] = step
    heapq.heappush(heap, (step, nr, nc))

Bottleneck routes (maximize the minimum capacity), minimum-effort paths and "latest possible departure" problems are all Dijkstra with a different combine step. Swapping max back to + answers a different question - the total climb, not the worst step.

Where you'll see it

Link-state routing protocols (OSPF, IS-IS) run Dijkstra on each router's view of the network to build forwarding tables. Map and navigation services start from Dijkstra and add heuristics and precomputation (A*, contraction hierarchies) to answer queries on continent-sized road graphs in milliseconds.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Edges 0->1 (1), 0->2 (5), 2->1 (-10). What does a finalize-once Dijkstra give for node 1, and why?

2. Why can a node appear in the heap several times, and what stops that from causing wrong answers?

3. On a height grid, the effort of a path is its largest single height step. Why does Dijkstra still find the minimum-effort path?

Key takeaways

• Dijkstra settles nodes in order of distance, using a min-heap; with non-negative weights, a popped node's distance is final.
• Push a new entry on every improvement and skip stale entries when popped (lazy deletion).
• Negative edges break the greedy argument - finalize-once versions go wrong, lazy versions can blow up; use Bellman-Ford.
• Any path cost that never shrinks when extended works: sums, maxima, bottlenecks.
• O((V + E) log V); unit weights reduce to BFS.