Dijkstra calcula caminos mínimos desde un origen en grafos con pesos no negativos. Selecciona repetidamente el vértice pendiente con menor distancia y relaja sus conexiones.
El algoritmo de Dijkstra resuelve el problema de caminos mínimos desde un origen hacia todos los vértices de un grafo ponderado. Fue propuesto por Edsger W. Dijkstra y se convirtió en una herramienta fundamental para rutas, redes y planificación.
Su estrategia es voraz: en cada etapa elige la mejor opción disponible y fija la distancia del vértice pendiente más cercano.
Dijkstra requiere que todas las aristas tengan pesos no negativos.
Los pesos pueden ser cero. Lo que no puede existir es una arista negativa, porque permitiría encontrar más adelante una ruta que reduzjera una distancia que el algoritmo ya consideró definitiva.
Una distancia tentativa es el mejor costo conocido hasta el momento, pero todavía podría mejorar. Cuando el vértice se extrae como mínimo, Dijkstra la convierte en definitiva.
| Estado | Significado |
|---|---|
| ∞ | Todavía no se conoce una ruta |
| Tentativa | Existe una ruta conocida, pero el vértice sigue pendiente |
| Definitiva | Se demostró que no existe una ruta más barata |
Al procesar la arista u → v, se compara la distancia actual de v con el costo de llegar pasando por u:
Si la alternativa no es menor, se conserva la ruta conocida. Cada mejora registra también el predecesor que permitirá reconstruir el camino.
Selecciona un vértice antes de iniciar. La simulación muestra cada extracción y relajación. En la tabla, los renglones celestes corresponden a distancias ya fijadas.
Distancias y padres
Acción actual
Cola de prioridad
Rosa indica el vértice o la arista del paso actual; celeste, vértices fijados; verde, vértices pendientes con distancia finita. Las aristas celestes forman el árbol de caminos mínimos.
Cuando u es el vértice pendiente con menor distancia, cualquier ruta alternativa hacia u que pase por otro vértice pendiente debe llegar primero a ese otro nodo. Su costo ya es al menos distancia[u].
Como las aristas restantes no tienen pesos negativos, continuar desde allí no puede reducir el costo por debajo de distancia[u]. Por eso la estimación de u puede fijarse con seguridad.
function dijkstraSimple(grafo, origen) {
const vertices = Object.keys(grafo);
const distancia = Object.fromEntries(vertices.map(v => [v, Infinity]));
const padre = Object.fromEntries(vertices.map(v => [v, null]));
const fijados = new Set();
distancia[origen] = 0;
while (fijados.size < vertices.length) {
let actual = null;
for (const v of vertices) {
if (!fijados.has(v) &&
(actual === null || distancia[v] < distancia[actual])) {
actual = v;
}
}
if (actual === null || distancia[actual] === Infinity) break;
fijados.add(actual);
for (const { destino, peso } of grafo[actual]) {
const alternativa = distancia[actual] + peso;
if (alternativa < distancia[destino]) {
distancia[destino] = alternativa;
padre[destino] = actual;
}
}
}
return { distancia, padre };
}Buscar linealmente el mínimo cuesta O(V) por iteración. Una cola de prioridad basada en un montículo permite extraer eficientemente el vértice con menor distancia tentativa.
Cuando una relajación mejora una distancia podemos disminuir su prioridad o insertar una nueva entrada. La segunda estrategia es común: al extraer una entrada desactualizada, simplemente se descarta.
function dijkstra(grafo, origen, colaPrioridad) {
const distancia = {}, padre = {};
for (const v of Object.keys(grafo)) {
distancia[v] = Infinity;
padre[v] = null;
}
distancia[origen] = 0;
colaPrioridad.insertar({ vertice: origen, distancia: 0 });
while (!colaPrioridad.estaVacia()) {
const actual = colaPrioridad.extraerMinimo();
if (actual.distancia !== distancia[actual.vertice]) continue;
for (const arista of grafo[actual.vertice]) {
const nueva = actual.distancia + arista.peso;
if (nueva < distancia[arista.destino]) {
distancia[arista.destino] = nueva;
padre[arista.destino] = actual.vertice;
colaPrioridad.insertar({
vertice: arista.destino,
distancia: nueva
});
}
}
}
return { distancia, padre };
}Supongamos que B entra en la cola con distancia 10 y después mejora a 6. Si insertamos una segunda entrada, ambas permanecen hasta ser extraídas.
La entrada con 6 se procesa primero. Cuando aparezca la de 10, ya estará desactualizada y no debe provocar nuevas relajaciones.
function reconstruir(padre, origen, destino) {
const camino = [];
let actual = destino;
while (actual !== null) {
camino.push(actual);
if (actual === origen) return camino.reverse();
actual = padre[actual];
}
return null; // destino inalcanzable
}Los predecesores de todos los destinos alcanzables forman un árbol de caminos mínimos con raíz en el origen.
Si solo interesa un destino t, el algoritmo puede finalizar cuando t es extraído como mínimo y fijado. Detenerse cuando t se descubre o entra en la cola sería prematuro: su distancia todavía podría mejorar.
Si la menor prioridad pendiente es infinito, no existe ningún camino desde el origen hacia los vértices restantes. Sus distancias continúan en infinito y sus padres en null.
Esto es normal en grafos desconectados o en grafos dirigidos cuyas aristas no permiten llegar a todas las regiones.
| Implementación | Tiempo | Uso recomendado |
|---|---|---|
| Matriz o búsqueda lineal | O(V²) | Grafos densos o pequeños |
| Lista + montículo binario | O((V + E) log V) | Grafos dispersos |
El espacio adicional es O(V) para distancias, padres, estados y cola, además de la representación del grafo.
Dijkstra supone que una distancia fijada no podrá mejorar. Una arista negativa desde un vértice procesado más tarde puede romper esa suposición.
No basta con que el costo total de algunos caminos sea positivo: la condición debe cumplirse para todas las aristas. Con pesos negativos se utiliza Bellman-Ford.
Dijkstra combina una selección voraz con relajaciones para convertir estimaciones tentativas en distancias definitivas. Es rápido y ampliamente utilizado, pero su corrección depende de que ninguna arista tenga peso negativo.
En el próximo tema estudiaremos Bellman-Ford, capaz de trabajar con pesos negativos y detectar ciclos de costo negativo.