Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 26/32

The shortest path: Dijkstra

✕
1/8

Fewer legs isn't fewer kilometers

BFS counts hops, as if every edge had the same length. On a map that's not true. The drawing has five towns in the region (Sahuayo, Jiquilpan, Venustiano Carranza, Cotija and Zamora) with the kilometers on each leg. The kilometers are made up for the exercise, not the real road distances.

From Sahuayo to Zamora there's a direct leg of 60, but going through Jiquilpan it's 8 + 45 = 53. BFS would say "direct, one hop". We need something that adds up weights.

86460455040ZamJiqSahVenCot
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The path with more legs is shorter in kilometers. With five towns you can eyeball it; with thousands of intersections, like a real map, you need an algorithm.

The whole lesson on one page

Fewer legs isn't fewer kilometers

BFS counts hops, as if every edge had the same length. On a map that's not true. The drawing has five towns in the region (Sahuayo, Jiquilpan, Venustiano Carranza, Cotija and Zamora) with the kilometers on each leg. The kilometers are made up for the exercise, not the real road distances.

From Sahuayo to Zamora there's a direct leg of 60, but going through Jiquilpan it's 8 + 45 = 53. BFS would say "direct, one hop". We need something that adds up weights.

86460455040ZamJiqSahVenCot
const km = { "Sah-Zam": 60, "Sah-Jiq": 8, "Jiq-Zam": 45 };

const directo = km["Sah-Zam"];
const porJiquilpan = km["Sah-Jiq"] + km["Jiq-Zam"];

console.log("direct:          1 leg, ", directo, "km");
console.log("via Jiquilpan:   2 legs,", porJiquilpan, "km");

The path with more legs is shorter in kilometers. With five towns you can eyeball it; with thousands of intersections, like a real map, you need an algorithm.

Dijkstra's idea

Edsger Dijkstra published it in 1959. Each vertex carries its best known distance from the start (at first, infinity; the start itself, 0). Then repeat:

  • Take the unsettled vertex with the smallest distance. That distance is now final: any other path would go through something farther away.
  • Relax its edges: if reaching a neighbor through here is shorter than what it had, update it and note where it came from.

This version finds the smallest by checking them all, so it costs O(V²). To rebuild the route, follow previo backwards from the destination.

const ady = {
  Sah: [["Jiq", 8], ["Ven", 6], ["Zam", 60], ["Cot", 50]],
  Jiq: [["Sah", 8], ["Ven", 4], ["Zam", 45]],
  Ven: [["Sah", 6], ["Jiq", 4]],
  Cot: [["Sah", 50], ["Zam", 40]],
  Zam: [["Sah", 60], ["Jiq", 45], ["Cot", 40]],
};

function dijkstra(origen) {
  const dist = {}, previo = {}, fijo = new Set();
  for (const v in ady) dist[v] = Infinity;
  dist[origen] = 0;
  while (fijo.size < Object.keys(ady).length) {
    // the closest unsettled one
    let v = null;
    for (const u in ady) if (!fijo.has(u) && (v === null || dist[u] < dist[v])) v = u;
    if (dist[v] === Infinity) break;   // what's left can't be reached
    fijo.add(v);
    for (const [w, km] of ady[v]) {
      if (dist[v] + km < dist[w]) {    // relax
        dist[w] = dist[v] + km;
        previo[w] = v;
      }
    }
  }
  return { dist, previo };
}

const { dist, previo } = dijkstra("Sah");
console.log(dist);

const ruta = ["Zam"];
while (previo[ruta[0]]) ruta.unshift(previo[ruta[0]]);
console.log(ruta.join(" -> "), dist.Zam, "km");
  • Zamora is 53 away via Jiquilpan, not 60 on the direct leg.
  • Jiquilpan is 8 away directly: via Venustiano Carranza it would be 6 + 4 = 10, and Dijkstra kept the smaller one.
  • The route comes from following previo from Zamora back to Sahuayo.

Faster with a heap

Finding the closest by checking them all is the expensive part. With last unit's priority queue it comes out in O(log V): every time a distance improves, push the pair [distance, vertex]. Old pairs for a vertex that has since improved may linger; when popped, they're recognized because their distance is bigger than the recorded one, and they're tossed. That makes it O((V + E) log V), which on a big map is the difference between an instant and a wait.

One condition: weights can't be negative. Dijkstra treats a distance as final as soon as it pops it, and a negative edge further on could improve it. For negative weights there's Bellman-Ford, which is slower.

const ady = {
  Sah: [["Jiq", 8], ["Ven", 6], ["Zam", 60], ["Cot", 50]],
  Jiq: [["Sah", 8], ["Ven", 4], ["Zam", 45]],
  Ven: [["Sah", 6], ["Jiq", 4]],
  Cot: [["Sah", 50], ["Zam", 40]],
  Zam: [["Sah", 60], ["Jiq", 45], ["Cot", 40]],
};

// Min-heap of [distance, vertex] pairs (unit 9's, compacted)
function meter(h, par) {
  h.push(par);
  let i = h.length - 1;
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (h[p][0] <= h[i][0]) break;
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}
function sacar(h) {
  const arriba = h[0], ultimo = h.pop();
  if (h.length > 0) {
    h[0] = ultimo;
    let i = 0;
    while (true) {
      const a = 2 * i + 1, b = 2 * i + 2;
      let m = i;
      if (a < h.length && h[a][0] < h[m][0]) m = a;
      if (b < h.length && h[b][0] < h[m][0]) m = b;
      if (m === i) break;
      [h[m], h[i]] = [h[i], h[m]];
      i = m;
    }
  }
  return arriba;
}

function dijkstra(origen) {
  const dist = { [origen]: 0 };
  const heap = [[0, origen]];
  let sacadas = 0, viejas = 0;
  while (heap.length > 0) {
    const [d, v] = sacar(heap);
    sacadas++;
    if (d > dist[v]) { viejas++; continue; }   // a better path was already found
    for (const [w, km] of ady[v]) {
      const nueva = d + km;
      if (dist[w] === undefined || nueva < dist[w]) {
        dist[w] = nueva;
        meter(heap, [nueva, w]);
      }
    }
  }
  console.log("pairs popped:", sacadas, "· stale:", viejas);
  return dist;
}

console.log(dijkstra("Sah"));
  • The distances are the same as the O(V²) version: 8, 6, 53 and 50.
  • One stale pair came out: [60, Zam], pushed before the 53 path through Jiquilpan was found. It was tossed without doing anything.