Why does this Dijkstra implementation keep the stale distance and miss the shorter path?

programming web dev
1

Hey everyone, I’m working on a route picker for a small delivery tool, and I’m trying to keep it simple with Dijkstra before I add more features. The weird part is it looks fine on light cases, but once a node gets discovered twice, I either keep the older cost or do extra work and the result drifts.

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

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

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

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

    for (const [next, weight] of graph[node]) {
      const nextCost = cost + weight;
      if (nextCost < dist[next]) {
        dist[next] = nextCost;
        pq.push([dist[next], next]);
      }
    }
  }

  return dist;
}

What am I missing about when a node is safe to mark seen here if I want to avoid wasted queue entries without locking in the wrong distance?

Hari

2

Your seen set is currently finalizing whatever queue entry got popped, not the node’s current shortest distance. That means an older entry can get locked in, not the newer shorter one.

Dijkstra is happy to have multiple queue entries for the same node. The trick is that only the entry matching dist[node] is still valid when it comes back out. Anything larger is stale and should be skipped, not marked as done.

The smallest fix is this:

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

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

  for (const [next, weight] of graph[node]) {
    const nextCost = cost + weight;
    if (nextCost < dist[next]) {
      dist[next] = nextCost;
      pq.push([nextCost, next]);
    }
  }
}

That cost !== dist[node] check is the whole point:

  • dist[node] does the real bookkeeping for the best path found so far.
  • cost !== dist[node] ensures old queue entries cannot relax neighbors using outdated costs.

So you avoid locking in the wrong value without needing seen.

A tiny version of the same idea is just this:

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

Using the same pq and dist approach, here’s a runnable case where B is discovered first with 10, then improved to 2, and the stale 10 entry gets ignored:

function shortestPath(graph, start) {
  const dist = {};
  const pq = [[0, start]];

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

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

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

    for (const [next, weight] of graph[node]) {
      const nextCost = cost + weight;
      if (nextCost < dist[next]) {
        dist[next] = nextCost;
        pq.push([nextCost, next]);
      }
    }
  }

  return dist;
}

const graph = {
  A: [["B", 10], ["C", 1]],
  B: [],
  C: [["B", 1]]
};

console.log(shortestPath(graph, "A"));
// { A: 0, B: 2, C: 1 }

If performance starts mattering, replace pq.sort() with a min-heap so the queue stops doing impressions of a sorted list.

Arthur

3

Dijkstra can have duplicate queue entries just fine; the bug is treating the first popped entry as final. Skip stale entries with if (cost !== dist[node]) continue and drop seen, so only the current shortest distance gets processed.

Hari

4

@HariSeldon, your pq.sort() line is also masking the real model a bit: the queue is just a bag of candidates, and dist[node] is the source of truth, so a stale [10, "B"] sitting there is harmless once dist["B"] already became 2.

Yoshiii