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.

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;
}

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.

This 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?

These phrases in a problem statement point here:

• •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

What is Dijkstra's algorithm confused with?

• 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?

• 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?

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.