Dijkstra's algorithm

How does Dijkstra's algorithm work?

Give every node a distance of infinity. The start node gets zero instead.

Put the start into a heap keyed by distance. The heap always hands back the nearest node.

Pop a node from the heap. If its stored distance is better than the popped one, skip it.

Otherwise the node is settled. Its distance is final and can never improve again.

For each outgoing edge, compare the stored distance with the route through this node. If the new one is shorter, store it and push it.

Repeat until the heap runs empty. Every reachable node has been settled once.

Sources: Wikipedia: Dijkstra's algorithm, Dijkstra (1959), A note on two problems in connexion with graphs

1. dist = A 0, B inf, C infThree edges: A to B at 1, A to C at 4. B reaches C at 2.
2. pop A and relaxB becomes 1 and C becomes 4.
3. pop B at 1, relax to CZero plus 1 plus 2 is 3, which beats the 4.
4. dist = A 0, B 1, C 3C is pushed again with the better distance.
5. pop C at 3, then C at 4The stale entry is skipped, since 3 is already better.

function dijkstra(n, adj, source) {
    const dist = new Array(n).fill(Infinity);
    dist[source] = 0;
    const heap = [[0, source]]; // [distance, node]
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // swap for a real heap in production
        const [d, u] = heap.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u] || []) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;
}

function dijkstra(n: number, adj: Array<Array<[number, number]>>, source: number): number[] {
    const dist = new Array<number>(n).fill(Infinity);
    dist[source] = 0;
    const heap: Array<[number, number]> = [[0, source]]; // [distance, node]
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // swap for a real heap in production
        const [d, u] = heap.shift()!;
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u] ?? []) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;
}

import heapq

def dijkstra(n, adj, source):
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj.get(u, []):
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

function dijkstra(int $n, array $adj, int $source): array {
    $dist = array_fill(0, $n, INF);
    $dist[$source] = 0;
    $heap = new SplPriorityQueue();
    $heap->insert($source, 0);
    while (!$heap->isEmpty()) {
        $u = $heap->extract();
        foreach ($adj[$u] ?? [] as [$v, $w]) {
            if ($dist[$u] + $w < $dist[$v]) {
                $dist[$v] = $dist[$u] + $w;
                $heap->insert($v, -$dist[$v]); // max-heap: negate for min-order
            }
        }
    }
    return $dist;
}

    public static int[] dijkstra(int n, List<List<int[]>> adj, int source) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        // {distance, node}, smallest distance first
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.add(new int[] { 0, source });
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;
            for (int[] edge : adj.get(u)) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    heap.add(new int[] { dist[v], v });
                }
            }
        }
        return dist;
    }

    public static int[] Dijkstra(int n, List<List<int[]>> adj, int source) {
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[source] = 0;
        // the node, keyed by its distance: smallest first
        var heap = new PriorityQueue<int, int>();
        heap.Enqueue(source, 0);
        while (heap.Count > 0) {
            heap.TryDequeue(out int u, out int d);
            if (d > dist[u]) continue;
            foreach (var edge in adj[u]) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    heap.Enqueue(v, dist[v]);
                }
            }
        }
        return dist;
    }

A worked example of Dijkstra's algorithm

How long a signal takes to reach everyone

A signal starts at one node and travels along weighted edges. Return the time until every node has it.

If some node cannot be reached at all, return minus one.

The signal problem is one shortest-path run from a single source.

The answer is the largest of the final distances. A node never reached leaves an infinity behind.

function networkDelayTime(times, n, k) {
    const graph = new Map();
    for (const [from, to, weight] of times) {
        if (!graph.has(from)) graph.set(from, []);
        graph.get(from).push([to, weight]);
    }

    const dist = new Map([[k, 0]]);
    const heap = new MinHeap((entry) => entry[0]); // entries are [distance, node]
    heap.push([0, k]);

    while (heap.size()) {
        const [d, node] = heap.pop();
        if (d > (dist.get(node) ?? Infinity)) continue; // a stale entry

        for (const [next, weight] of graph.get(node) ?? []) {
            const candidate = d + weight;
            if (candidate < (dist.get(next) ?? Infinity)) {
                dist.set(next, candidate);
                heap.push([candidate, next]);
            }
        }
    }

    if (dist.size < n) return -1;
    return Math.max(...dist.values());
}

When should you use Dijkstra's algorithm?

Use Dijkstra's algorithm when the problem statement says “cheapest/shortest path with weighted edges”, “non-negative edge weights” or “minimum total cost to reach every node”. A solution built on it usually runs in O(E log V).

• •cheapest/shortest path with weighted edges
• •non-negative edge weights
• •minimum total cost to reach every node
• •network delay time / route cost, not fewest roads
• •weighted graph, single-source shortest paths

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Dijkstra's algorithm confused with?

Dijkstra's algorithm is most often confused with Graph BFS / DFS, Binary heap / priority queue, Greedy (exchange argument) and Topological sort (Kahn's algorithm).

• Graph BFS / DFS: A queue counts hops, so it assumes every edge costs the same. A heap handles real weights.
• Binary heap / priority queue: The heap is the tool this runs on. That page is about the container itself.
• Greedy (exchange argument): Settling the nearest node is a greedy choice. It only holds while no weight is negative.
• Topological sort (Kahn's algorithm): On a graph with no cycles the order relaxes edges without a heap. That is faster and allows negatives.

Common mistakes with Dijkstra's algorithm

• Running it with negative weights

  A settled node could still improve, so the greedy step fails. Use Bellman-Ford instead.

• Not skipping stale heap entries

  A node can be pushed several times with different distances. Compare against the stored value on pop.

• Marking a node settled on push

  A node pushed early can get a better route later. Settle it on pop, never on push.

• Using a plain queue

  A queue counts edges rather than weight. That only matches when every edge costs the same.

Which interview problems use Dijkstra's algorithm?

Interview problems solved with Dijkstra's algorithm include Network delay time, Cheapest flights within k stops, Path with minimum effort, Swim in rising water, Path with maximum probability, Minimum cost to reach the last cell and Second shortest path.

• Network delay time: The plain form: the answer is the largest distance.
• Cheapest flights within k stops: A stop limit adds a second dimension to the state.
• Path with minimum effort: The cost of a path is its single worst step.
• Swim in rising water: The same, with a maximum instead of a sum.
• Path with maximum probability: Multiply instead of adding, and keep the largest.
• Minimum cost to reach the last cell: A grid is a graph with four edges per cell.
• Second shortest path: Keep the two best distances for each node.

What is the time and space complexity of Dijkstra's algorithm?

The target complexity of Dijkstra's algorithm is O(E log V).

V nodes and E edges give O(E log V) with a heap. Negative weights break it, so use Bellman-Ford.