Dijkstra's Algorithm

A Bit of History

In 1956, Dutch computer scientist Edsger W. Dijkstra was thinking about the shortest route between two cities in the Netherlands — partly to demonstrate the capabilities of a new computer to a general audience. By his own later account, he designed the algorithm in about twenty minutes, without pencil or paper, while having coffee with his fiancée at a café terrace in Amsterdam. He didn't publish it until 1959, in a short three-page paper that also introduced an algorithm for minimum spanning trees (closely related to Kruskal's algorithm and Prim's algorithm, covered in an upcoming deep dive). Dijkstra later reflected that the algorithm's elegance came from deliberately avoiding pencil and paper — forcing him to keep the method simple enough to hold entirely in his head.

Working Principle

Dijkstra's algorithm solves the single-source shortest path problem on a weighted graph with non-negative edge weights. It generalizes BFS's "process closest-first" idea: instead of a plain queue (which assumes every edge costs "1"), it uses a min-priority queue keyed by tentative distance, always expanding the currently-closest unfinalized vertex next.

Maintain a tentative distance \(d[v]\) for every vertex (initialized to \(\infty\), except \(d[\text{source}]=0\)). Repeatedly extract the vertex \(u\) with the smallest tentative distance that hasn't been finalized yet, mark it finalized, and relax every outgoing edge \((u,v)\): if \(d[u] + w(u,v) < d[v]\), update \(d[v]\) to that smaller value.

$$\textbf{Relaxation: } d[v] \leftarrow \min\big(d[v],\ d[u] + w(u,v)\big)$$

Worked Example

Consider a small weighted graph: \(A \to B\) (weight 4), \(A \to C\) (weight 1), \(C \to B\) (weight 1), \(B \to D\) (weight 1), \(C \to D\) (weight 5).

flowchart LR
    A -->|4| B
    A -->|1| C
    C -->|1| B
    B -->|1| D
    C -->|5| D
            

Notice how \(d[B]\) drops from 4 to 2 once \(C\) is finalized and its outgoing edge \(C \to B\) is relaxed — the direct edge \(A \to B\) (weight 4) was never actually the shortest route; going through \(C\) (weight \(1+1=2\)) is cheaper. This is exactly why Dijkstra's algorithm must consider all edges out of a vertex before that vertex's neighbors can be trusted as final.

Why Greedy Works Here

This is the direct-proof and induction machinery from Part 1 in action. Claim: when a vertex \(u\) is extracted from the priority queue (finalized), \(d[u]\) already equals the true shortest-path distance from the source.

Proof by induction on the order vertices are finalized. Base case: the source is finalized first with \(d[\text{source}]=0\), trivially correct. Inductive step: suppose every previously finalized vertex has a correct final distance. Let \(u\) be the next vertex extracted, with the smallest tentative distance among all unfinalized vertices. Any path to \(u\) must, at some point, leave the "finalized" set for the last time — crossing some edge \((x, y)\) where \(x\) is finalized and \(y\) is not. Since edge weights are non-negative, the length of that path is at least \(d[x] + w(x,y) \geq d[y] \geq d[u]\) (the last inequality holds because \(u\) was chosen to have the smallest tentative distance). So no unfinalized route can beat \(d[u]\) — it is already optimal.

Complexity Analysis

With a binary-heap priority queue, each of the \(V\) extract-min operations costs \(O(\log V)\), and each of the \(E\) relaxations may trigger a \(O(\log V)\) decrease-key (or, in the common simplified implementation, a fresh \(O(\log V)\) insertion, discarding stale entries lazily):

$$\text{Time: } O((V+E)\log V) \qquad \text{Space: } O(V)$$

A naive \(O(V^2)\) array-based implementation (scan all unfinalized vertices for the minimum, every time) is actually faster on very dense graphs where \(E\) approaches \(V^2\) — a good reminder that asymptotic complexity depends on the graph's shape, not just its algorithm.

Implementation

import heapq
from collections import defaultdict

def dijkstra(adj, source):
    """
    adj: dict[vertex] -> list[(neighbor, weight)], weights must be >= 0.
    Returns dist: dict[vertex] -> shortest distance from source.
    """
    dist = {source: 0}
    visited = set()
    heap = [(0, source)]      # (tentative distance, vertex)

    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue           # stale entry — a shorter one was already processed
        visited.add(u)

        for v, weight in adj[u]:
            nd = d + weight
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return dist

adj = defaultdict(list, {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 1), ("D", 5)],
    "D": [],
})

print(dijkstra(adj, "A"))   # {'A': 0, 'C': 1, 'B': 2, 'D': 3}

#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <limits>
using namespace std;

unordered_map<string, long long>
dijkstra(unordered_map<string, vector<pair<string, int>>>& adj, const string& source) {
    unordered_map<string, long long> dist;
    unordered_set<string> visited;
    // min-heap of (distance, vertex)
    priority_queue<pair<long long, string>,
                   vector<pair<long long, string>>,
                   greater<>> heap;

    dist[source] = 0;
    heap.push({0, source});

    while (!heap.empty()) {
        auto [d, u] = heap.top(); heap.pop();
        if (visited.count(u)) continue;   // stale entry
        visited.insert(u);

        for (auto& [v, w] : adj[u]) {
            long long nd = d + w;
            if (!dist.count(v) || nd < dist[v]) {
                dist[v] = nd;
                heap.push({nd, v});
            }
        }
    }
    return dist;
}

int main() {
    unordered_map<string, vector<pair<string, int>>> adj = {
        {"A", {{"B", 4}, {"C", 1}}},
        {"B", {{"D", 1}}},
        {"C", {{"B", 1}, {"D", 5}}},
        {"D", {}}
    };

    auto dist = dijkstra(adj, "A");
    cout << "Distance A->D: " << dist["D"] << endl;  // 3
    return 0;
}

import java.util.*;

class Dijkstra {
    record Edge(String to, int weight) {}

    static Map<String, Long> dijkstra(Map<String, List<Edge>> adj, String source) {
        Map<String, Long> dist = new HashMap<>();
        Set<String> visited = new HashSet<>();
        PriorityQueue<long[]> heap = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        Map<Long, String> idToVertex = new HashMap<>(); // simple id trick omitted for brevity

        dist.put(source, 0L);
        // Using a small wrapper since Java PQ needs comparable primitives cleanly:
        PriorityQueue<Object[]> pq = new PriorityQueue<>(Comparator.comparingLong(o -> (long) o[0]));
        pq.add(new Object[]{0L, source});

        while (!pq.isEmpty()) {
            Object[] top = pq.poll();
            long d = (long) top[0];
            String u = (String) top[1];
            if (visited.contains(u)) continue;    // stale entry
            visited.add(u);

            for (Edge e : adj.getOrDefault(u, Collections.emptyList())) {
                long nd = d + e.weight();
                if (!dist.containsKey(e.to()) || nd < dist.get(e.to())) {
                    dist.put(e.to(), nd);
                    pq.add(new Object[]{nd, e.to()});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Map<String, List<Edge>> adj = new HashMap<>();
        adj.put("A", List.of(new Edge("B", 4), new Edge("C", 1)));
        adj.put("B", List.of(new Edge("D", 1)));
        adj.put("C", List.of(new Edge("B", 1), new Edge("D", 5)));
        adj.put("D", List.of());

        Map<String, Long> dist = dijkstra(adj, "A");
        System.out.println("Distance A->D: " + dist.get("D"));  // 3
    }
}

Real-World Applications

Exercises

1. Run Dijkstra's algorithm by hand on the graph in the worked example, but starting from vertex \(C\) instead of \(A\).
2. Construct a small graph with a negative edge weight where Dijkstra's algorithm produces an incorrect shortest-path distance, and explain exactly which step of the correctness proof fails.
3. Modify the Python implementation above to also track and reconstruct the shortest path (not just its length) using a parent map, matching the technique from the BFS deep dive.
4. Challenge: Explain why running Dijkstra's algorithm from a single source and stopping early the moment your specific target vertex is finalized is still correct and often faster in practice, even though it doesn't compute distances to every vertex.

Limitations