Problema resuelto al detalle
-
Nodo 1 a una arista del origen con un coste de 4 5 pasos
El nodo 1 está a una arista del origen, con un coste de 4 — y el algoritmo indica que su distancia es 3. Siga el orden de fijación y averigüe de dónde sale el 3.
-
Dijkstra fija los nodos en orden de distancia, sin volver a visitarlos nunca. Ese ordenamiento constituye el algoritmo entero y toda la demostración: cuando se fija un nodo, no puede existir una ruta más económica hasta él, ya que cualquier otra ruta tendría que pasar por un nodo no fijado que ya está más distante.
-
Desde el origen, las dos aristas directas ofrecen distancias tentativas de 4 y 2. Ninguna es definitiva aún: son cotas superiores.
-
El más cercano es el nodo 3, con una distancia de 2, por lo que se fija en primer lugar. Al relajar sus aristas se encuentra una ruta al nodo 1 con un coste de 2 + 1 = 3, que mejora a la arista directa de 4. Este es el paso que responde a la pregunta: el camino más económico hacia un vecino no tiene por qué ser la arista directa hacia él.
-
El nodo 1 se fija en 3 y, al relajar desde allí, se alcanza el nodo 2 con un coste de 8.
-
El nodo 4 es alcanzable con un coste de 8 a través del nodo 3, y la alternativa a través del nodo 2 cuesta 8 + 3 = 11, de modo que prevalece la más corta.
Respuesta
La herramienta muestra distancias de 3, 8, 2, 8 y un camino más corto de 0 → 3 → 4. La lección está en el nodo 1: una arista directa no es un camino más corto, y la fijación voraz es lo que permite averiguar esto con un coste bajo en lugar de exponencial. La garantía exige, sin embargo, un requisito: pesos no negativos. Con una arista negativa, un nodo fijado tempranamente puede mejorarse más tarde, y la demostración del paso 1 se desmorona. Haga clic en el ajuste preestablecido de arista negativa y observe cómo falla en ambas direcciones a la vez: el nodo 3 devuelve −1, que no es una distancia producida por ninguna ruta, y la reconstrucción del camino se rinde por completo con «sin camino — los predecesores forman un bucle». Números erróneos y ninguna ruta, de un algoritmo que es demostrablemente correcto desde el momento en que todos los pesos son no negativos.
-
Referencias (2)
- The three-page paper, in which the shortest-path algorithm is the SECOND of the two problems: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
- The algorithm the negative-edge preset points you to, which tolerates negative weights and detects a negative cycle instead of answering as though there were none: R. Bellman, "On a routing problem." Quarterly of Applied Mathematics 16(1), 87–90, 1958.