El algoritmo de Dijkstra responde “¿cuál es la forma más barata de llegar a cada nodo desde una fuente?” en un grafo ponderado — el motor detrás del enrutamiento GPS, enrutamiento OSPF y entrega de paquetes.

Funciona expandiendo vorazmente el nodo no visitado más cercano, usando una cola de prioridad mínima para siempre elegir el mejor nodo frontera. Su único requisito estricto: sin aristas de peso negativo.

Cómo Funciona

1. Inicializa: establece dist[fuente] = 0, todos los demás ∞. Inserta la fuente en la cola de prioridad.
2. Extrae el mínimo: elimina el nodo con la distancia conocida más pequeña de la cola de prioridad.
3. Relaja aristas: para cada vecino, verifica si enrutar a través del nodo actual da un camino más corto. Si es así, actualiza su distancia y padre.
4. Repite: hasta que la cola de prioridad esté vacía. Cada distancia extraída ahora es final.

Idea Clave

El paso voraz es válido precisamente porque los pesos de las aristas son no negativos: una vez que un nodo se extrae de la cola con su distancia mínima, ningún camino futuro (más largo) podría posiblemente mejorarlo. Esta es la análoga de camino más corto de la propiedad de corte.

La operación relax — “si dist[u] + w < dist[v], actualiza dist[v]” — es todo el motor. Todo lo demás solo decide el orden de las relajaciones: siempre la más prometedora primero.

Ejemplo Trabajado

Ejecuta Dijkstra en el grafo ponderado del visualizador, fuente S:

Distancias más cortas: S=0, A=2, B=4, C=5, D=5, E=7, T=8. Observa que B→D mejora D de 9 a 5 después de que A ya fue procesado — Dijkstra re-relaja vecinos y la cola de prioridad corrige el orden. Observa la tabla de distancias en el visualizador actualizarse a medida que cada nodo se finaliza.

Casos Extremos y Trampas

• “Aristas negativas — Dijkstra retorna respuestas incorrectamente silenciosamente: la extracción voraz es inválida. Usa Bellman-Ford.”
• “Nodos desconectados — los nodos inalcanzables mantienen dist = ∞: reprórtalos como tales.”
• Múltiples caminos más cortos — cualquiera es válido; los punteros padre reconstruyen uno de ellos.
• Grafos densos — una cola simple basada en arreglo da O(V²), que supera a un heap cuando E ≈ V². La versión con heap O((V+E) log V) es mejor para grafos dispersos.

Comparación con Otros Algoritmos de Camino

Aplicaciones

• Navegación GPS — camino más corto en carretera entre dos puntos
• Enrutamiento de redes — protocolo OSPF
• Servicios de mapas — tiempos de viaje y distancias
• Logística — optimización de rutas de entrega
• Redes sociales — cadenas de conexión más cortas

Trayectoria de Práctica

1. Traza a mano Dijkstra en el grafo del visualizador comenzando en A, registrando la tabla de distancias cada ronda.
2. Explica por qué extraer un nodo del min-heap finaliza su distancia dados pesos no negativos.
3. Construye un grafo pequeño con una arista negativa y muestra dónde falla Dijkstra.
4. Reconstruye el camino más corto de S a T usando punteros padre.
5. Compara el comportamiento de Dijkstra en grafos dispersos vs densos y cuándo preferir O(V²).