patternjavascriptMajor

Dijkstra's shortest path requires a min-heap and only works with non-negative weights

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

dijkstrashortest pathweighted graphmin heappriority queuebellman-ford

Problem

Dijkstra is often implemented with a sorted array (O(n^2)) or incorrectly applied to graphs with negative edge weights, producing wrong results. Without a priority queue it is too slow for large graphs.

Solution

Use a min-heap keyed by distance. Start with source at distance 0. Greedily process the closest unvisited node: relax its edges, push updated distances to the heap. Skip nodes already finalized. Negative weights break Dijkstra — use Bellman-Ford instead.

Why

The greedy choice is safe because distances only increase with non-negative weights. Once you finalize the shortest distance to a node, no future relaxation can improve it. Negative edges violate this invariant.

Gotchas

Lazy deletion: push updated (dist, node) to heap without removing the old entry. Skip the node if the popped distance > recorded distance
Negative edge weights require Bellman-Ford (O(VE)) or SPFA
For dense graphs, adjacency matrix + simple array can beat heap-based Dijkstra

Code Snippets

Dijkstra with lazy deletion min-heap

function dijkstra(graph, src) {
  // graph: Map<node, Array<[neighbor, weight]>>
  const dist = new Map([[src, 0]]);
  const heap = new MinHeap(); // from earlier snippet
  heap.push([0, src]); // [dist, node]

  while (heap.size) {
    const [d, u] = heap.pop();
    if (d > (dist.get(u) ?? Infinity)) continue; // outdated entry
    for (const [v, w] of (graph.get(u) ?? [])) {
      const nd = d + w;
      if (nd < (dist.get(v) ?? Infinity)) {
        dist.set(v, nd);
        heap.push([nd, v]);
      }
    }
  }
  return dist;
}

Context

Shortest path in weighted directed or undirected graphs with non-negative edge weights

Revisions (0)

No revisions yet.