Distancia total
-
Suma de pesos en la ruta.
Modelos de redes · Investigación de operaciones
Ruta Más Corta: Algoritmo de Dijkstra
El algoritmo más famoso de teoría de grafos (Edsger Dijkstra, 1956). Encuentra el camino de menor costo entre dos nodos en un grafo con pesos no negativos. Base de GPS, ruteo de red, logística y miles de aplicaciones más.
Saltos (hops)
-
Aristas en la ruta.
Nodos visitados
-
Total en el grafo.
Aristas totales
-
En el grafo.
Tipo
-
Dirigido/No dirigido.
Iteraciones
-
Nodos procesados.
Visualización del grafo
Arista normal
Arista en ruta óptima
Nodo en ruta
Distancias mínimas desde el origen
Dijkstra calcula simultáneamente la ruta más corta desde el origen a TODOS los demás nodos.
| Nodo | Distancia desde origen | Predecesor | Ruta |
|---|
El algoritmo de Dijkstra en lenguaje claro
- El problema
- Dado un grafo con nodos y aristas que tienen un peso (distancia, costo, tiempo), encontrar el camino de menor peso total entre dos nodos. Es uno de los problemas más estudiados de la computación: GPS para encontrar la mejor ruta, internet para enviar paquetes, ferrocarriles, telecomunicaciones, redes sociales (grados de separación).
- La idea de Dijkstra (1956)
- Empieza con todas las distancias en infinito excepto el origen (0). En cada paso:
- Toma el nodo no visitado con menor distancia tentativa.
- Para cada vecino de ese nodo: si ir vía este nodo es más corto que su distancia actual, actualiza.
- Marca el nodo como visitado.
- Repite hasta que todos los nodos estén visitados o el destino esté visitado.
- Por qué funciona
- La propiedad clave: el camino más corto de A a Z pasa por subcaminos que también son los más cortos. Si ir A→B→C es lo mejor para llegar a C, entonces A→B es lo mejor para llegar a B. Esta "subestructura óptima" permite construir la solución global combinando soluciones locales óptimas.
- Complejidad
- Con implementación con cola de prioridad (heap): O((V + E) log V). Para los grafos pequeños de esta calculadora (hasta ~12 nodos) corre instantáneamente. Para redes reales con millones de nodos (Google Maps), se usan optimizaciones como A*, contraction hierarchies, ALT.
- Limitación crítica: pesos no negativos
- Dijkstra NO funciona con pesos negativos. Si una arista tiene peso negativo, el algoritmo puede dar resultados incorrectos porque asume que una vez "visitado" un nodo ya no hay manera de mejorar su distancia, lo cual deja de ser cierto con pesos negativos. Para grafos con pesos negativos se usa Bellman-Ford (O(VE) pero más lento).
- Variantes y problemas relacionados
-
- Floyd-Warshall: distancias mínimas entre TODOS los pares de nodos. O(V³).
- A*: Dijkstra con heurística (típico en videojuegos y GPS modernos).
- Bellman-Ford: maneja pesos negativos. Detecta ciclos negativos.
- Johnson: combina Bellman-Ford y Dijkstra para todos los pares.
- K-shortest paths (Yen): encontrar las K rutas más cortas.
- Aplicaciones reales
-
- GPS y navegación: Google Maps, Waze (variantes optimizadas).
- Internet routing: OSPF (Open Shortest Path First) usa Dijkstra.
- Logística: rutas óptimas de transporte y distribución.
- Videojuegos: pathfinding de personajes.
- Redes sociales: distancia entre usuarios (grados de separación).
- Aerolíneas: ruteo de vuelos optimizando tiempo o costo.
- Robótica: planificación de rutas de robots móviles.
- Generalización a otros problemas
- Cambiando lo que representan los pesos, Dijkstra resuelve:
- Pesos = tiempo: ruta más rápida.
- Pesos = combustible: ruta más económica.
- Pesos = -log(probabilidad): camino de máxima probabilidad.
- Pesos = riesgo: camino más seguro.
- Pesos = capacidad inversa: ruta de menor congestión.
Trivia: Dijkstra inventó el algoritmo en 20 minutos en un café de Ámsterdam en 1956, sin papel ni lápiz, mientras esperaba que su esposa eligiera ropa. Lo publicó tres años después. Es uno de los algoritmos más usados en la historia de la computación.