Dijkstra y Caminos Mínimos

Dijkstra es el algoritmo de caminos más cortos más famoso. La idea: mantén la distancia mínima conocida desde el origen a cada nodo. Empieza en el origen con distancia 0. En cada paso, toma el nodo no visitado con menor distancia (usando un Min-Heap para hacerlo eficientemente), y actualiza las distancias de sus vecinos. Repite hasta procesar todos los nodos. La restricción: no funciona con pesos negativos (para eso existe Bellman-Ford).

Dijkstra está detrás de muchos sistemas que usas diariamente. El GPS de tu teléfono usa una variación de Dijkstra (con A* para mayor eficiencia) para calcular la ruta más rápida. Los routers de internet usan OSPF, un protocolo basado en Dijkstra, para determinar por dónde enviar los paquetes.

Los juegos de estrategia usan pathfinding con A* (Dijkstra con una heurística) para mover personajes por el mapa. Entender Dijkstra es entender la infraestructura digital moderna.

// Dijkstra con Min-Heap (simplificado con array)
function dijkstra(grafo, inicio) {
  // grafo = { A: [[B, 4], [C, 2]], B: [[D, 3]], ... }
  const distancias = {};
  const visitados = new Set();
  
  // Inicializar distancias a Infinity
  for (const nodo in grafo) distancias[nodo] = Infinity;
  distancias[inicio] = 0;
  
  // Priority queue simulada (en prod usar un heap real)
  const cola = [[0, inicio]]; // [distancia, nodo]
  
  while (cola.length > 0) {
    // Extraer el nodo con menor distancia
    cola.sort((a, b) => a[0] - b[0]);
    const [dist, nodo] = cola.shift();
    
    if (visitados.has(nodo)) continue;
    visitados.add(nodo);
    
    for (const [vecino, peso] of (grafo[nodo] || [])) {
      const nuevaDist = dist + peso;
      if (nuevaDist < distancias[vecino]) {
        distancias[vecino] = nuevaDist;
        cola.push([nuevaDist, vecino]);
      }
    }
  }
  
  return distancias;
}

// Ejemplo: red de ciudades
const red = {
  "Madrid":   [["Barcelona", 621], ["Sevilla", 540], ["Valencia", 357]],
  "Barcelona":[["Madrid", 621], ["Valencia", 349]],
  "Sevilla":  [["Madrid", 540], ["Valencia", 650]],
  "Valencia": [["Madrid", 357], ["Barcelona", 349], ["Sevilla", 650]]
};

console.log(dijkstra(red, "Sevilla"));
// { Sevilla: 0, Madrid: 540, Valencia: 650, Barcelona: 889 }
// Nota: Sevilla→Valencia→Barcelona (650+349=999) vs calculado: 889
// En realidad: Sevilla→Madrid(540)→Barcelona(621+540=... no)
// Sevilla→Madrid(540)→Valencia(540+357=897)...Barcelona=897+349=1246
// O Sevilla→Valencia(650)→Barcelona(650+349=999)

// Bellman-Ford: cuando hay pesos negativos
// Floyd-Warshall: caminos más cortos entre TODOS los pares
// Algoritmo de Prim / Kruskal: árbol de expansión mínima