Dijkstra's Shortest Path, From Scratch

Dijkstra's algorithm finds the shortest path from a source vertex to every other vertex in a graph with non-negative edge weights. It is worth understanding not as a memorized procedure but as a direct consequence of one invariant.

The invariant

Maintain a tentative distance $d[v]$ for every vertex, initialized to

Process vertices in increasing order of finalized distance. The key claim: when a vertex $u$ is removed from the frontier with the smallest tentative distance, $d[u]$ is already optimal. This holds precisely because edge weights are non-negative — any later path to $u$ must pass through an already-larger distance, so it cannot improve $d[u]$.

Relaxation

Each time we finalize $u$, we relax its outgoing edges. For an edge $(u, v)$ with weight $w(u, v)$:

Complexity

With a binary heap, each vertex is extracted once ($V$ extractions) and each edge can push one entry ($E$ operations), and every heap operation is $O(\log V)$:

A Fibonacci heap amortizes decrease-key to $O(1)$, giving the theoretical optimum $O(E + V \log V)$ — but the constants make a binary heap faster in practice for the graphs you will actually meet.

Implementation

Java's PriorityQueue has no decrease-key, so we use the standard lazy-deletion trick: push a fresh entry on every improvement and skip stale ones on poll.

package dev.fiveyear.graph;
 
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
 
public final class Dijkstra {
 
    /** graph.get(u) = list of {to, weight}; returns shortest distance to every vertex. */
    public static int[] shortestPaths(List<List<int[]>> graph, int source) {
        int[] dist = new int[graph.size()];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
 
        // min-heap of {distance, vertex}
        PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        heap.add(new long[] {0, source});
 
        while (!heap.isEmpty()) {
            long[] top = heap.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) {
                continue; // stale entry — already finalized with a smaller distance
            }
 
            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                long nd = d + edge[1];
                if (nd < dist[v]) {
                    dist[v] = (int) nd;
                    heap.add(new long[] {nd, v});
                }
            }
        }
        return dist;
    }
}

The stale-entry check on line 22 is what makes lazy deletion correct: a vertex may sit in the heap several times, but only its smallest entry does real work; the rest are discarded in O(1).

When Dijkstra is the wrong tool

• Negative edges break the invariant — use Bellman–Ford.
• All-pairs shortest paths on a dense graph — Floyd–Warshall is simpler.
• Unweighted graphs — a plain BFS is O(V + E) with no heap at all.