Algoritmo de Dijkstra

El algoritmo de Dijkstra, desarrollado por Edsger Dijkstra en 1956, encuentra el camino más corto desde un vértice origen hasta todos los demás vértices en un grafo ponderado con pesos de arista no negativos. Es la base de la navegación GPS, el enrutamiento de redes (protocolo OSPF) y servicios de mapas como Google Maps.

Idea clave: expansión voraz

El algoritmo de Dijkstra mantiene un conjunto de vértices cuya distancia más corta desde el origen ya se conoce (el conjunto de vértices cerrados) y una cola de prioridad de candidatos ordenados por su mejor estimación de distancia actual. En cada paso extrae el vértice abierto más cercano, fija su distancia y relaja sus aristas salientes.

La corrección se apoya en que los pesos son no negativos: una vez que un vértice queda cerrado, ningún camino futuro puede mejorar su distancia. Con pesos negativos esta garantía desaparece, y hay que usar Bellman-Ford en su lugar.

El algoritmo

Entrada: un grafo dirigido ponderado \(G = (V, E, w)\) con \(w(u,v) \geq 0\), y un vértice origen \(s\).

Salida: \(d[v]\) = distancia más corta de \(s\) a \(v\), y \(\text{prev}[v]\) = predecesor de \(v\) en ese camino.

Inicialización:

\[d[s] = 0, \quad d[v] = \infty \;\forall v \neq s, \quad \text{prev}[v] = \text{Ninguno} \;\forall v\]

Se insertan todos los vértices en una cola de prioridad mínima \(Q\) con clave \(d[v]\).

Bucle principal: mientras \(Q\) no esté vacío:

  1. Extraer \(u = \arg\min_{v \in Q} d[v]\) (vértice con menor distancia tentativa).
  2. Para cada vecino \(v\) de \(u\) con peso de arista \(w(u,v)\):
    • Relajación: si \(d[u] + w(u,v) < d[v]\), actualizar \(d[v] \leftarrow d[u] + w(u,v)\) y \(\text{prev}[v] \leftarrow u\).
  3. Eliminar \(u\) de \(Q\).

El paso de relajación es el núcleo del algoritmo: comprueba si el camino que pasa por \(u\) es más corto que el mejor camino conocido hasta \(v\).

Ejemplo paso a paso

Encuentra los caminos más cortos desde A en este grafo:

Grafo dirigido ponderado del ejemplo paso a paso de Dijkstra con cinco nodos

Tabla de iteraciones (origen = A):

Paso Cerrado \(d[A]\) \(d[B]\) \(d[C]\) \(d[D]\) \(d[E]\)
Inicio - 0 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
1 A 0 4 2 \(\infty\) \(\infty\)
2 C 0 4 2 5 10
3 B 0 4 2 5 10
4 D 0 4 2 5 7
5 E 0 4 2 5 7

Caminos más cortos desde A:

  • A \(\to\) B: coste 4 (directo)
  • A \(\to\) C: coste 2 (directo)
  • A \(\to\) D: coste 5 (A-C-D)
  • A \(\to\) E: coste 7 (A-C-D-E)

Mismo grafo con el árbol de caminos más cortos resaltado mostrando las rutas óptimas desde A hasta todos los demás nodos

Complejidad

La complejidad depende de la implementación de la cola de prioridad:

Implementación Extract-min Decrease-key Complejidad total
Array (naive) \(O(V)\) \(O(1)\) \(O(V^2)\)
Montículo binario \(O(\log V)\) \(O(\log V)\) \(O((V+E)\log V)\)
Montículo de Fibonacci \(O(\log V)\) \(O(1)\) amortizado \(O(E + V\log V)\)

Para grafos densos (\(E \approx V^2\)): la implementación con array es óptima con \(O(V^2)\). Para grafos dispersos (\(E = O(V)\) o \(O(V\log V)\)): el montículo binario da \(O(V\log V)\), mucho mejor. El montículo de Fibonacci es teóricamente óptimo pero raramente se usa en la práctica por sus grandes constantes.

La mayoría de redes reales (redes de carreteras, tablas de enrutamiento de internet) son dispersas, así que la versión con cola de prioridad es el estándar.

Reconstruir el camino más corto

El array \(\text{prev}[]\) almacena el predecesor de cada vértice en el camino más corto. Para recuperar el camino de \(s\) hasta un destino \(t\):

camino <- c()
actual <- t
while (!is.null(actual)) {
  camino <- c(actual, camino)
  actual <- prev[actual]
}
# camino es: s -> ... -> t

Este recorrido hacia atrás va de \(t\) a \(s\) en tiempo \(O(V)\).

Cuándo falla Dijkstra: pesos negativos

⚠️ El algoritmo de Dijkstra no es correcto con pesos de arista negativos

Con pesos negativos, cerrar un vértice no garantiza que se haya encontrado su distancia más corta: un camino posterior que pase por una arista negativa podría ser más corto. Ejemplo:

  • A \(\to\) B: peso 3
  • A \(\to\) C: peso 5
  • C \(\to\) B: peso \(-4\)

Dijkstra cierra B con distancia 3. Pero el camino A-C-B tiene distancia \(5 + (-4) = 1 < 3\). Como Dijkstra nunca reconsidera B tras cerrarlo, devuelve la respuesta incorrecta.

Para grafos con pesos negativos pero sin ciclos negativos, usa Bellman-Ford: complejidad \(O(VE)\), pero maneja los pesos negativos correctamente. Si hay ciclos negativos (no existe camino más corto), Bellman-Ford también los detecta.

Grafo pequeño que muestra en qué caso falla Dijkstra cuando hay una arista de peso negativo

Variantes y extensiones

Variante Problema Algoritmo
Pesos negativos Caminos más cortos Bellman-Ford \(O(VE)\)
Caminos más cortos entre todos los pares Cada par \((u,v)\) Floyd-Warshall \(O(V^3)\)
Grafo no ponderado Camino más corto por saltos BFS \(O(V+E)\)
Heurística disponible Destino único A* (más rápido en la práctica)
Grafo dinámico Las aristas cambian con el tiempo D* o LPA*

El algoritmo A* extiende Dijkstra con una función heurística \(h(v)\) que estima la distancia de \(v\) al destino, concentrando la búsqueda y reduciendo el número de vértices explorados. Es el estándar en pathfinding para videojuegos y robótica.

💡 Dijkstra en R

library(igraph)

# Construir el grafo
g <- graph_from_data_frame(
  data.frame(from=c("A","A","B","B","C","C","D"),
             to  =c("B","C","C","D","D","E","E"),
             weight=c(4,2,1,5,3,8,2)),
  directed=TRUE
)

# Distancias más cortas desde A
distances(g, v="A", weights=E(g)$weight)

# Camino más corto de A a E (con la secuencia de vértices)
shortest_paths(g, from="A", to="E", weights=E(g)$weight)$vpath

# Caminos más cortos entre todos los pares
distances(g, weights=E(g)$weight)