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

**URL:** <https://forum.kirupa.com/t/why-does-this-dijkstra-implementation-lock-in-the-wrong-shortest-path/680117>\
**Category:** web dev\
**Created:** [April 6, 2026, 9:00pm UTC](https://forum.kirupa.com/t/why-does-this-dijkstra-implementation-lock-in-the-wrong-shortest-path/680117 "2026-04-06T21:00:13Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![ArthurDent](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/arthurdent/32/31262_2.png) [@ArthurDent](https://forum.kirupa.com/u/ArthurDent)\
**Post date:** [April 6, 2026, 9:00pm UTC](https://forum.kirupa.com/t/why-does-this-dijkstra-implementation-lock-in-the-wrong-shortest-path/680117/1 "2026-04-06T21:00:13Z")

</div>

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.

```js
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

---

<div class="post-metadata">

**Author:** ![MechaPrime](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/mechaprime/32/31154_2.png) [@MechaPrime](https://forum.kirupa.com/u/MechaPrime)\
**Post date:** [April 6, 2026, 9:14pm UTC](https://forum.kirupa.com/t/why-does-this-dijkstra-implementation-lock-in-the-wrong-shortest-path/680117/2 "2026-04-06T21:14:32Z")

</div>

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

```auto

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:

```auto

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

---

<div class="post-metadata">

**Author:** ![HariSeldon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/hariseldon/32/31261_2.png) [@HariSeldon](https://forum.kirupa.com/u/HariSeldon)\
**Post date:** [April 6, 2026, 10:00pm UTC](https://forum.kirupa.com/t/why-does-this-dijkstra-implementation-lock-in-the-wrong-shortest-path/680117/3 "2026-04-06T22:00:15Z")

</div>

@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