Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 26/32

El camino más corto: Dijkstra

✕
1/8

Menos tramos no es menos kilómetros

BFS cuenta saltos, como si todas las aristas midieran lo mismo. En un mapa no es así. En el dibujo hay cinco pueblos de la región (Sahuayo, Jiquilpan, Venustiano Carranza, Cotija y Zamora) con los kilómetros sobre cada tramo. Los kilómetros son inventados para el ejercicio, no los de la carretera.

De Sahuayo a Zamora hay un tramo directo de 60, pero pasando por Jiquilpan son 8 + 45 = 53. BFS diría «directo, un salto». Hace falta algo que sume pesos.

86460455040ZamJiqSahVenCot
leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

El camino con más tramos es el más corto en kilómetros. Con cinco pueblos se ve a ojo; con miles de cruces, como en un mapa de verdad, hace falta un algoritmo.

Toda la lección en una página

Menos tramos no es menos kilómetros

BFS cuenta saltos, como si todas las aristas midieran lo mismo. En un mapa no es así. En el dibujo hay cinco pueblos de la región (Sahuayo, Jiquilpan, Venustiano Carranza, Cotija y Zamora) con los kilómetros sobre cada tramo. Los kilómetros son inventados para el ejercicio, no los de la carretera.

De Sahuayo a Zamora hay un tramo directo de 60, pero pasando por Jiquilpan son 8 + 45 = 53. BFS diría «directo, un salto». Hace falta algo que sume pesos.

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("directo:       1 tramo, ", directo, "km");
console.log("por Jiquilpan: 2 tramos,", porJiquilpan, "km");

El camino con más tramos es el más corto en kilómetros. Con cinco pueblos se ve a ojo; con miles de cruces, como en un mapa de verdad, hace falta un algoritmo.

La idea de Dijkstra

Edsger Dijkstra lo publicó en 1959. Cada vértice lleva su mejor distancia conocida desde el origen (al principio, infinito; el origen, 0). Luego se repite:

  • Toma el vértice no fijado con la distancia más chica. Esa distancia ya es definitiva: cualquier otro camino pasaría por algo más lejos.
  • Relaja sus aristas: si llegar a un vecino por aquí es más corto que lo que tenía, se actualiza y se anota de dónde vino.

Esta versión busca el más chico revisando todos, así que cuesta O(V²). Para reconstruir la ruta se sigue previo hacia atrás desde el destino.

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) {
    // el no fijado más cercano
    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;   // lo que queda no se alcanza
    fijo.add(v);
    for (const [w, km] of ady[v]) {
      if (dist[v] + km < dist[w]) {    // relajar
        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 queda a 53 por Jiquilpan, no a 60 por el tramo directo.
  • Jiquilpan queda a 8 directo: por Venustiano Carranza serían 6 + 4 = 10, y Dijkstra se quedó con el menor.
  • La ruta sale de seguir previo desde Zamora hasta Sahuayo.

Más rápido con un montículo

Buscar el más cercano revisando todos es lo caro. Con la cola de prioridad de la unidad anterior se saca en O(log V): cada vez que una distancia mejora, se mete la pareja [distancia, vértice]. Pueden quedar parejas viejas de un vértice que ya mejoró; al sacarlas se reconocen porque su distancia es mayor que la anotada, y se tiran. Así cuesta O((V + E) log V), que en un mapa grande es la diferencia entre un instante y una espera.

Una condición: los pesos no pueden ser negativos. Dijkstra da por definitiva una distancia en cuanto la saca, y una arista negativa más adelante podría mejorarla. Para pesos negativos existe Bellman-Ford, más lento.

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]],
};

// Montículo mínimo de parejas [distancia, vértice] (el de la unidad 9, compacto)
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; }   // ya había un camino mejor
    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("parejas sacadas:", sacadas, "· viejas:", viejas);
  return dist;
}

console.log(dijkstra("Sah"));
  • Las distancias son las mismas que con la versión O(V²): 8, 6, 53 y 50.
  • Salió una pareja vieja: [60, Zam], que entró antes de descubrir el camino de 53 por Jiquilpan. Se tiró sin hacer nada.