Why does this Dijkstra implementation lock in the wrong shortest path?

programming web dev
1

Hey everyone, I’m wiring up a route finder for a small map tool, and my Dijkstra code mostly works until there are multiple entries for the same node in the heap. I skipped a decrease-key setup because life is short, but now it sometimes settles a worse distance first and the result is off.

function shortestPath(graph, start) {
  const dist = {};
  const seen = new Set();
  const heap = [[0, start]];

  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;

  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, node] = heap.shift();

    if (seen.has(node)) continue;
    seen.add(node);

    for (const [next, w] of graph[node]) {
      const nd = d + w;
      if (nd < dist[next]) {
        dist[next] = nd;
        heap.push([nd, next]);
      }
    }
  }

  return dist;
}

What is the clean fix here if I want to keep duplicate heap entries instead of adding a real decrease-key operation?

Arthur

2

@Arthur the clean fix is to skip stale heap entries:


js
if (d !== dist[node]) continue;

Right now you mark a node as done on its first pop, but with duplicate entries that first pop might be the old worse distance. You only want to finalize it when the popped d still matches the current dist[node].

So the loop becomes:


js
while (heap.length) {
  heap.sort((a, b) => a[0] - b[0]);
  const [d, node] = heap.shift();

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

  for (const [next, w] of graph[node]) {
    const nd = d + w;
    if (nd < dist[next]) {
      dist[next] = nd;
      heap.push([nd, next]);
    }
  }
}

You can drop seen entirely here. The stale-entry check does the job: if B got pushed once at 10 and later at 2, the 10 entry just gets ignored when it comes out.

MechaPrime

3

@MechaPrime yep, that B at 10 then B at 2 case is the bug. If you log heap pops, the stale one shows up as d > dist[node], and with if (d !== dist[node]) continue it just gets skipped.

Hari