O que o painel Shortest path resolve O painel Shortest path executa quatro algoritmos sobre o mesmo grafo ponderado: Dijkstra, A*, Bellman–Ford e Floyd–Warshall. Cada conjunto de linhas nomeia seu método, imprime a distância e a rota e — para as duas buscas de fonte única que rastreiam — a ordem de fixação em que os vértices foram finalizados. Os grafos são construídos na bancada de teoria dos grafos compartilhada; o botão Directed, os pesos das arestas e a caixa de colagem da matriz de adjacência se aplicam.
Como executar cada algoritmo 01 Carregue um grafo e defina as extremidades. Construa uma predefinição ou cole uma matriz de adjacência, depois escolha Source e Target; uma construção por predefinição os redefine para o primeiro e o último nó. 02 Dijkstra responde distância, caminho e ordem de fixação, e recusa qualquer grafo com aresta negativa — o erro nomeia a aresta e aponta para Bellman–Ford. 03 A\ adiciona um seletor de heurística (manhattan / euclidean / zero) e informa os nós expandidos em relação ao Dijkstra, a escala de heurística realmente usada e se a heurística é consistente e portanto ótima. 04 Bellman–Ford informa as rodadas de relaxamento, lista as distâncias finais por nó e sinaliza um ciclo negativo se existir. 05 Floyd–Warshall preenche a matriz de distâncias a partir de uma fonte, marca nós de ciclo negativo e pode responder qualquer par origem/destino pela mesma tabela.
Leituras calculadas Lido do painel:
Configuração
Leitura
Grafo padrão de 6 nós, Dijkstra A → F
distância 13 ; caminho A → C → B → D → E → F ; ordem de fixação A → C → B → D → E → F ; d[B] 3 , d[C] 2 , d[D] 8 , d[E] 10
Grade 4 × 5, Dijkstra 1-1 → 4-5
distância 7 ; a ordem de fixação lista os 20 nós; caminho 1-1 → 1-2 → 2-2 → 3-2 → 3-3 → 3-4 → 3-5 → 4-5
Grafo padrão, A* com euclidean
distância 13 , mesmo caminho; nós expandidos 6 / Dijkstra 6 ; escala de heurística 0.01346 ; consistente ótima Yes
Predefinição Negative weights, Bellman–Ford a partir de S
3 rodadas de relaxamento; d[S] 0 , d[A] 3 , d[B] 5 , d[C] 0 , d[D] 3 ; ciclo negativo None
Predefinição Negative weights, Floyd–Warshall S → D
distância 3 ; caminho S → B → A → C → D ; nós de ciclo negativo None
O d[C] = 2 do Dijkstra vem da aresta direta A–C, e d[B] = 3 de A → C → B, não da aresta mais pesada A–B de peso 4 . O Bellman–Ford alcança os mesmos valores num grafo com uma aresta −3, e o Floyd–Warshall encontra S → B → A → C → D encadeando uma aresta negativa e uma positiva.
Por que o A\* imprime uma escala Coordenadas da tela e pesos de arestas são grandezas diferentes, então o A* mede a heurística sobre o layout e a escala pelo maior fator que ainda mantém h(u) ≤ w(u,v) + h(v) em cada arco. No grafo padrão a escala euclidean é 0.01346 , e as três heurísticas expandem os mesmos 6 nós que o Dijkstra. A linha consistente-ótima é a promessa de que a distância retornada é exata.
Limites
Pesos não negativos para Dijkstra e A\*. Ambos recusam uma aresta negativa em vez de retornar uma distância grande demais; mude para Bellman–Ford no mesmo painel para a predefinição Negative weights. Uma fonte por execução. Não há Dijkstra multi-fonte nem Johnson para todos os pares; o Floyd–Warshall é a opção de todos os pares, com custo cúbico. O painel também não lê listas de arestas de um arquivo nem exporta uma rota — grave a matriz de adjacência no espaço de trabalho e leve-a para as matrix tools , para o painel Spanning tree para a fiação mais barata ou para Flow & matching para perguntas de capacidade.
A fronteira das arestas negativas Construa a predefinição Negative weights (S → A 4, S → B 5, A → C −3, B → A −2, B → C 4, C → D 3) e pressione Dijkstra com Source S. O painel recusa com a mensagem "Edge 3 has weight -3. Dijkstra cannot handle negative weights (a settled distance could still be lowered) — use Bellman–Ford instead" em vez de um número errado plausível. Mude o algoritmo para Bellman–Ford e S → C lê 0 , uma distância que a fixação gulosa do Dijkstra jamais teria produzido. O A* carrega a mesma recusa; sua mensagem também aponta para Bellman–Ford.
Onde é útil Prova de otimalidade para um passeio A ordem de fixação do Dijkstra é a prova de que as distâncias finais estão certas: cada vértice é finalizado uma vez e nunca revisitado. No grafo padrão a aresta direta A–B pesa 4 , mas a rota por C custa 3 , e a ordem A → C → B → D → E → F mostra C finalizado antes de B — o painel exibe seu próprio argumento de correção.
Ensinar por que heurísticas precisam de escala Coloque o A* na heurística zero e a execução é Dijkstra com contabilidade (escala 1 ); coloque euclidean no grafo padrão disposto e a escala cai para 0.01346 , então a estimativa nunca pode ultrapassar o custo real enquanto a rota permanece exata.
Custos negativos em planejamento A predefinição Negative weights modela um crédito entre duas etapas. O Bellman–Ford responde S → D em 3 ; o Floyd–Warshall confirma o mesmo valor, e nenhum reporta um ciclo negativo, então a cadeia de melhoria S → B → A → C → D termina.
Privacidade A edição do grafo e cada execução de shortest path acontecem no seu navegador; nada é enviado.
Referências
Wikipedia, Dijkstra's algorithm , en.wikipedia.org (访问日期:2026-10-07)— fixação gulosa e pesos não negativos.
Wikipedia, Bellman–Ford algorithm , en.wikipedia.org (访问日期:2026-10-07)— rodadas de relaxamento e detecção de ciclo negativo.
Wikipedia, Floyd–Warshall algorithm , en.wikipedia.org (访问日期:2026-10-07)— programação dinâmica para todos os pares.
Wikipedia, A* search algorithm , en.wikipedia.org (访问日期:2026-10-07)— heurísticas admissíveis e consistentes.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— caminhos mais curtos de fonte única.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07