Dijkstra’s Algorithm

Edsger Dijkstra invented this in 1956 (and reportedly designed it in his head over a coffee in twenty minutes). It’s the single most important shortest-path algorithm — fast, simple, broadly applicable. Non-negative edge weights, single source, any graph structure.

The idea, in one sentence:

Repeatedly pluck the closest unfinished vertex from a priority queue, mark it done, and relax all its outgoing edges.

That’s it. Everything else is bookkeeping.

The algorithm

Worked example

Source A. Graph:

Tracing through:

Final: dist[A]=0, dist[B]=3, dist[C]=1, dist[D]=8, dist[E]=10. Matches our intuition from the introduction.

The template

vector<long long> dijkstra(int n, vector<vector<pair<int,int>>>& adj, int src) {
    // adj[u] = list of (v, weight)
    const long long INF = LLONG_MAX;
    vector<long long> dist(n, INF);
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;              // stale
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

import heapq
 
def dijkstra(n, adj, src):
    # adj[u] = list of (v, weight)
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                            # stale
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

long[] dijkstra(int n, List<List<int[]>> adj, int src) {
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    dist[src] = 0;
    pq.offer(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] cur = pq.poll();
        long d = cur[0];
        int u = (int) cur[1];
        if (d > dist[u]) continue;              // stale
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new long[]{dist[v], v});
            }
        }
    }
    return dist;
}

Why correctness

When Dijkstra pops vertex u from the heap, the current dist[u] is the true shortest distance from s to u. Proof sketch:

Suppose for contradiction there’s a shorter path P from s to u not yet discovered. P must leave the set of “finalized” vertices at some point — let x be the first vertex on P that’s not yet finalized. Then dist[x] ≤ (length of P up to x) ≤ (length of P) < dist[u].

But Dijkstra always pops the smallest tentative distance. If dist[x] < dist[u], then x would be popped before u — contradiction.

The proof critically uses “length of P up to x” ≤ “length of P” — that step is true only because edge weights are non-negative. With negative edges, extending a path can shrink it, and the proof falls apart.

Complexity

For sparse graphs (E = O(V)), binary heap is O(V log V). For dense graphs (E = O(V²)), the array-based O(V²) is actually faster because there’s no log V factor on the relaxations. In practice, just use the binary-heap version — the constant factors dominate everything in interview-sized inputs.

Path reconstruction

Add a parent array, set parent[v] = u whenever you relax v through u. Then walk back from the target:

def dijkstra_with_path(n, adj, src, dst):
    dist = [float('inf')] * n
    parent = [-1] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                heapq.heappush(pq, (dist[v], v))
    # reconstruct
    if dist[dst] == float('inf'):
        return None
    path = []
    cur = dst
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]

Common variants and gotchas

Variant: distance with constraints

“Shortest path with at most K stops.” The state is no longer just a vertex — it’s (vertex, stops_used). Run Dijkstra on the expanded state space. We’ll see this exact pattern in Cheapest Flights Within K Stops.

Variant: maximin / minimax paths

“Find the path that minimizes the maximum edge weight” — the Path with Minimum Effort problem. Same skeleton, but instead of summing edge weights you take the max. Relaxation becomes dist[v] = min(dist[v], max(dist[u], w)). The greedy choice still works because max is monotone in the same way + is for non-negatives.

Gotcha: dense graphs and the O(V²) trap

If your adjacency representation is a V × V matrix and you call Dijkstra naively, each “for each neighbor” loop costs O(V) regardless of how few neighbors there really are. Either convert to a sparse adjacency list, or use the array-based O(V²) Dijkstra directly.

Gotcha: negative weights

Bears repeating: Dijkstra is incorrect on negative weights, even if there’s no negative cycle. The algorithm may finalize a vertex’s distance early and never revisit it. If you see negatives in the problem statement, switch to Bellman-Ford.

Quick check

Next: when negative weights are in play, Dijkstra is out and Bellman-Ford takes over.