Problema resolvido na íntegra
-
O nó 1 a uma aresta da origem com um custo de 4 5 passos
O nó 1 está a uma aresta da origem, com um custo de 4 — e o algoritmo indica a sua distância como sendo 3. Percorra a ordem de fixação e descubra de onde vem o 3.
-
O algoritmo de Dijkstra fixa os nós por ordem de distância, sem nunca os revisitar. Essa ordenação é todo o algoritmo e toda a demonstração: quando um nó é fixado, não pode existir nenhum percurso mais barato até ele, pois qualquer percurso desse tipo teria de passar por um nó não fixado que já se encontra mais distante.
-
A partir da origem, as duas arestas diretas dão distâncias provisórias de 4 e 2. Nenhuma é ainda definitiva — são limites superiores.
-
O mais próximo é o nó 3 com 2, pelo que é o primeiro a ser fixado. O relaxamento das suas arestas encontra um percurso para o nó 1 com um custo de 2 + 1 = 3, o que supera a aresta direta de 4. Este é o passo que responde à pergunta: o caminho mais barato para um vizinho não tem de ser a aresta direta até ele.
-
O nó 1 é fixado em 3, e o relaxamento a partir daí alcança o nó 2 em 8.
-
O nó 4 é alcançável em 8 através do nó 3, e a alternativa através do nó 2 custa 8 + 3 = 11, pelo que prevalece o mais curto.
Resposta
A ferramenta apresenta distâncias de 3, 8, 2, 8 e um caminho mais curto de 0 → 3 → 4. A lição está no nó 1: uma aresta direta não é um caminho mais curto, e a fixação ambiciosa é o que torna essa descoberta eficiente em vez de exponencial. A garantia tem, contudo, um requisito — pesos não negativos. Com uma aresta negativa, um nó fixado cedo pode vir a ser melhorado mais tarde, e a demonstração do passo 1 deixa de ser válida. Clique na predefinição de arestas negativas e veja o algoritmo falhar em ambas as direções de uma só vez: o nó 3 surge com −1, que não é uma distância produzida por nenhum percurso, e a reconstrução do caminho desiste por completo com “sem caminho — os predecessores formam um ciclo”. Números errados e nenhum percurso, num algoritmo cuja correção é demonstrada assim que todos os pesos são não negativos.
-
Referências (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.