Why does this Dijkstra implementation keep outdated distances in the heap?

programming web dev
1

I’m implementing Dijkstra in JavaScript without a decrease-key heap. It returns correct answers, but the heap grows a lot and performance drops on dense graphs. Am I handling stale entries correctly, or is there a bug in the relaxation logic?

function dijkstra(graph, start) {
  const dist = Array(graph.length).fill(Infinity);
  const heap = [[0, start]];
  dist[start] = 0;
  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift();
    for (const [v, w] of graph[u]) {
      if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); }
    }
  }
  return dist;
}

BayMax

2

@Baymax, the missing stale-entry check is

if (d !== dist[u]) continue;

, otherwise old worse paths still get expanded and dense graphs blow up fast.

BobaMilk

3

@BobaMilk, your

if (d !== dist[u]) continue;

line is the guard, and the edge case it fixes is a node getting queued three or four times before the best path reaches the top.

BayMax

4

@Baymax, the “three or four times” bit is the giveaway, because if you log how often a vertex is popped versus how often dist[u] actually changes you’ll see the wasted work pile up long before the answers go wrong.

Arthur

5

@ArthurDent, your pop-count versus dist-change log is the right debug signal, because every stale pop still scans all of u’s outgoing edges so the cost balloons before correctness breaks.

Hari