Algoritmo de Dijkstra: ruta más corta en grafos ponderados

Características clave

El algoritmo es voraz: selecciona repetidamente el nodo no procesado con la menor distancia tentativa y relaja sus aristas salientes. Los elementos importantes incluyen:

• Vértices y aristas: nodos y conexiones con pesos numéricos.
• Pesos no negativos: necesarios para garantizar la corrección.
• Distancias tentativas: estimaciones provisionales del camino más corto que se actualizan durante la ejecución.

Cómo funciona

A grandes rasgos, los pasos son:

• Inicializar en cero la distancia del nodo inicial y en infinito la de todos los demás.
• Seleccionar el nodo no visitado con la distancia más pequeña.
• Para cada vecino, calcular una distancia candidata a través del nodo seleccionado y actualizarla si es menor (relajación).
• Marcar el nodo seleccionado como visitado y repetir hasta procesar todos los nodos alcanzables.

Complejidad y variaciones

El rendimiento depende de la estructura de datos usada para seleccionar el nodo de menor distancia. Con un montículo binario, la complejidad es aproximadamente O((V + E) log V). Un montículo de Fibonacci la reduce teóricamente a O(E + V log V). En un grafo denso, con matriz de adyacencia, puede implementarse en O(V^2). Las implementaciones prácticas equilibran memoria y sobrecarga frente a los límites teóricos.

Historia, usos y limitaciones

Nombrado en honor a Edsger W. Dijkstra, quien publicó el método en 1959, el algoritmo se volvió fundamental en la informática. Entre sus aplicaciones habituales están el enrutamiento de caminos más cortos en GPS y protocolos de enrutamiento de Internet, la búsqueda de rutas en videojuegos y la optimización de recursos. Su principal limitación es que no puede manejar pesos negativos en las aristas; cuando deben considerarse pesos negativos o ciclos negativos, se utilizan algoritmos como Bellman-Ford.