Dijkstra's algorithm

Overview

Dijkstra's algorithm finds the shortest path from one source to every other node in a graph with non-negative edge weights. It repeatedly takes the unvisited node with the smallest known distance, finalizes it, and relaxes its outgoing edges (tries to improve neighbors' distances through it).

A min-heap keyed by distance makes this O((V + E) log V). The greedy choice is safe because with non-negative weights, no later path can ever be shorter than the current smallest distance. With negative edges that guarantee breaks, and you need Bellman-Ford instead.

When to use it

• Shortest path or minimum cost with non-negative weights.
• Network delay, travel time, cheapest route, minimum effort.
• Grid problems where moves have different costs.
• State-space search where each state has a cost (Dijkstra on (node, extra state)).

Problem patterns it solves

Where it is used in real software

Key terms

dist[v]

Best known distance from the source to v.

Relaxation

If dist[u] + w < dist[v], update dist[v] and push it to the heap.

Finalized

When a node is popped with its current distance, that distance is optimal.

Stale entry

A heap entry whose distance is larger than dist[v]; skip it.

How it works, step by step

1. 1
   Initialize

   dist[source] = 0 and all others Infinity. Push [0, source] to a min-heap.

2. 2
   Pop the smallest distance

   Take [d, u] from the heap.

3. 3
   Skip stale entries

   If d > dist[u], a better path was already found; continue.

4. 4
   Relax each edge u -> v with weight w

   If d + w < dist[v], set dist[v] = d + w and push [dist[v], v].

5. 5
   Repeat until the heap is empty

   Or stop early when the target is popped.

Shortest distances from A

Edges: A-B 4, A-C 1, C-B 2, B-D 1, C-D 5

The shortest path to D is A -> C -> B -> D with cost 4, even though the direct-looking edges suggested 5 or 6. Stale heap entries are how the simple version handles updated distances without a decrease-key operation.

Implementation

1// Uses the PriorityQueue class from the Heap guide2function dijkstra(n, edges, source) {3  const graph = Array.from({ length: n }, () => []);4  for (const [u, v, w] of edges) graph[u].push([v, w]);5 6  const dist = new Array(n).fill(Infinity);7  dist[source] = 0;8  const heap = new PriorityQueue((a, b) => a[0] - b[0]);9  heap.push([0, source]);10 11  while (heap.size) {12    const [d, u] = heap.pop();13    if (d > dist[u]) continue; // stale entry14    for (const [v, w] of graph[u]) {15      if (d + w < dist[v]) {16        dist[v] = d + w;17        heap.push([dist[v], v]);18      }19    }20  }21  return dist;22}23 24// 743. Network Delay Time (1-indexed nodes)25function networkDelayTime(times, n, k) {26  const dist = dijkstra(n + 1, times, k).slice(1);27  const worst = Math.max(...dist);28  return worst === Infinity ? -1 : worst;29}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using Dijkstra with negative edges.

  Fix: Its greedy finalization becomes wrong; use Bellman-Ford or SPFA.

• Not skipping stale entries.

  Fix: Check if (d > dist[u]) continue, or the algorithm does extra work and may give wrong counts.

• Marking visited when pushing.

  Fix: A node's distance is only final when popped.

• Integer overflow when adding weights in Java.

  Fix: Skip nodes with MAX_VALUE distance, or use long.

Interview questions

Practice problems