Dijkstra's Algorithm

How Dijkstra works

The algorithm maintains:

• dist[v] — the best known distance from the source to v, initially ∞ for everyone except the source itself (0).
• visited — the set of nodes whose final distance is locked in.
• queue — a min-priority queue of unvisited nodes keyed by their current dist.

The loop repeatedly extracts the unvisited node u with the smallest dist[u], marks it visited, and relaxes each outgoing edge (u, v, w) — if dist[u] + w < dist[v], update dist[v] and push (dist[v], v) onto the queue.

The greedy invariant: once a node is extracted, its distance is final. No later relaxation can improve it because every other unvisited node already has dist ≥ this one (we extracted the minimum), and weights are non-negative — so any path through an unvisited node would only add to the total.

Why edge weights must be non-negative

The greedy invariant is the whole correctness argument. It depends on this fact: "if dist[u] is the minimum among unvisited, no future update can lower it." With non-negative weights, that's true — moving to another node and back to u would only add edge weights, never subtract.

With a negative edge weight, future moves can decrease total distance, so the locked-in dist might actually be wrong. Counter-example: source → A (weight 1), source → B (weight 2), B → A (weight -10). Dijkstra extracts A with dist=1 first, locks it in. Then extracts B (dist=2) and relaxes B → A, finding dist=2 + (-10) = -8 — but A is already locked. Wrong answer.

For graphs with negative weights, use Bellman-Ford (always works, O(V·E), can detect negative cycles).

Dijkstra vs other shortest-path algorithms

	Dijkstra	BFS	Bellman-Ford	A*
Edge weights	Non-negative	None (unweighted)	Any (incl. negative)	Non-negative
Time	O((V+E) log V)	O(V + E)	O(V·E)	O(b^d) — depends on heuristic
Space	O(V)	O(V)	O(V)	O(b^d) frontier
Detects negative cycles	No	N/A	Yes	No
Goal-directed?	No (computes all distances)	No	No	Yes (heuristic)
Best for	Single-source on weighted graph	Unweighted graph	Possible negative weights	Single target with good heuristic

When to use Dijkstra

• GPS / map routing. Edge weights are travel time or distance — both non-negative. The full single-source distance map computed by Dijkstra lets navigation re-route in real time as you move.
• Network routing protocols. OSPF (Open Shortest Path First) and IS-IS use Dijkstra to compute shortest paths through a network. Each router runs Dijkstra over its link-state database.
• Computer graphics — pathfinding in games. When the heuristic is hard to define (varied terrain costs, no known goal direction), plain Dijkstra is often used. A* is preferred when a heuristic exists.
• Dependency-cost computation. "What's the cheapest way to build target X given various transformations with costs?"

JavaScript implementation

// Requires the MinHeap class from the heap article — entries are [distance, node].
function dijkstra(graph, source) {
  const dist = new Map();
  const prev = new Map();
  for (const node of Object.keys(graph)) {
    dist.set(node, Infinity);
    prev.set(node, null);
  }
  dist.set(source, 0);

  const heap = new MinHeap();
  heap.push([0, source]);

  while (heap.size()) {
    const [d, u] = heap.pop();
    if (d > dist.get(u)) continue; // stale entry — skip

    for (const [v, w] of graph[u] || []) {
      const alt = d + w;
      if (alt < dist.get(v)) {
        dist.set(v, alt);
        prev.set(v, u);
        heap.push([alt, v]);
      }
    }
  }
  return { dist, prev };
}

// Reconstruct shortest path from source to target
function shortestPath(graph, source, target) {
  const { dist, prev } = dijkstra(graph, source);
  if (dist.get(target) === Infinity) return null;
  const path = [];
  for (let n = target; n !== null; n = prev.get(n)) path.unshift(n);
  return { distance: dist.get(target), path };
}

Note the "stale entry" check: when we relax an edge and a node's distance improves, we push a new [d, v] onto the heap without removing the old entry (that would require decrease-key). When the old entry surfaces, its distance is stale — skip it. This adds at most a constant factor and keeps the heap simple.

Python implementation

import heapq
from math import inf

def dijkstra(graph, source):
    dist = {node: inf for node in graph}
    prev = {node: None for node in graph}
    dist[source] = 0

    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue  # stale

        for v, w in graph.get(u, []):
            alt = d + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heapq.heappush(heap, (alt, v))

    return dist, prev

Famous Dijkstra problems

Path with Minimum Effort (LeetCode 1631)

Given a 2D grid of heights, find the path from top-left to bottom-right that minimizes the maximum absolute difference between consecutive cells. Variant of Dijkstra where the path cost is max of edge weights instead of sum — the relaxation rule changes from alt = dist[u] + w to alt = max(dist[u], w). Same algorithm, same heap, modified update rule.

Cheapest Flights Within K Stops

Standard Dijkstra plus a stop counter. Each heap entry becomes [cost, node, stopsRemaining]; only relax neighbors when stops remain. Time O(K · E · log(K · E)) since the same node can be visited K times with different stop counts.

Common bugs and edge cases

• Using Dijkstra with negative weights. The greedy invariant breaks. Use Bellman-Ford or, if no negative cycles, transform via Johnson's algorithm.
• Forgetting the stale-entry check. Without "if d > dist.get(u): continue", you'll process the same node multiple times, doing redundant work and possibly wrong updates.
• O(V²) array implementation when graph is sparse. If E is much less than V², the heap version is dramatically faster. Profile before assuming the array version is fine.
• Infinity comparison without proper sentinel. JavaScript's Infinity works correctly. Other languages need explicit handling — Python's math.inf, Java's Long.MAX_VALUE with overflow checks.
• Trying to use Dijkstra for longest paths. Longest simple paths in general graphs is NP-hard. Negating edge weights doesn't work either (negative weights break Dijkstra). For DAGs only, longest path is polynomial via topological sort.