- Atual
- Tem distância
- Aresta usada
- Caminho
- Ciclo negativo
Algoritmo de Bellman–Ford
O algoritmo de Dijkstra falha quando uma aresta tem comprimento negativo, como uma estrada que lhe paga uma portagem em vez de a cobrar. O algoritmo de Bellman–Ford não: limita-se a verificar cada aresta vezes sem conta até nada melhorar, e consegue até dizer quando um ciclo faz as distâncias descer sem fim. Clique num nó para começar a partir dele e avance passagem a passagem. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Cada aresta tem sentido único, como mostra a sua seta, e o número nela é o seu comprimento, que pode ser negativo. Clique num nó para o tornar a origem; mude o clique para Destino e clique noutro nó para ver no fim o caminho mais curto até ele. O número em cada nó é a sua distância até agora. Marque Adicionar um ciclo negativo para ver como o Bellman–Ford encontra um. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Clique num nó para o tornar a origem. Para ver um caminho no fim, mude o clique para Destino e clique noutro nó.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
- Marque Adicionar um ciclo negativo para ver o Bellman–Ford encontrar um. Novo grafo cria outro grafo para experimentar.
Como funciona o Bellman–Ford
Dê à origem a distância 0 e a todos os outros nós infinito. Depois faça passagens: em cada passagem, verifique cada aresta u → v uma vez. Se u tem distância e dist(u) mais o comprimento da aresta é menor do que dist(v), baixe dist(v) e guarde u como o caminho até lá. Após a passagem k, todos os caminhos mais curtos que usam no máximo k arestas são conhecidos. Um caminho mais curto visita cada nó no máximo uma vez, por isso tem no máximo n − 1 arestas, e n − 1 passagens bastam sempre. Se uma passagem inteira não alterar nada, a pesquisa pode parar mais cedo.
Encontrar um ciclo negativo
Se as arestas de um ciclo somam menos de zero, dar mais uma volta torna sempre um caminho mais curto, por isso não há caminho mais curto nenhum. O Bellman–Ford repara nisso: após n − 1 passagens, mais uma passagem não deveria alterar nada. Se uma aresta ainda puder ser relaxada, há um ciclo negativo alcançável a partir da origem, e seguir para trás os nós guardados a partir dessa aresta leva até ele. Na aplicação, o ciclo é desenhado a vermelho.
Perguntas frequentes
O que é o algoritmo de Bellman–Ford?
Um algoritmo que encontra os caminhos mais curtos de uma origem para todos os outros nós num grafo cujas arestas podem ter comprimentos negativos. Relaxa cada aresta em passagens repetidas, e assinala um ciclo negativo se for possível alcançar um a partir da origem.
Porque é que o algoritmo de Dijkstra falha com arestas negativas?
O Dijkstra torna definitiva a distância de um nó assim que ele é o mais próximo na fila. Uma aresta negativa encontrada mais tarde ainda pode levar de volta a esse nó por um caminho mais curto, por isso a distância definitiva pode estar errada. O Bellman–Ford nunca torna uma distância definitiva cedo demais; continua a verificar cada aresta.
Porquê n − 1 passagens?
Um caminho mais curto nunca precisa de visitar um nó duas vezes, por isso tem no máximo n − 1 arestas. Cada passagem estende os caminhos mais curtos conhecidos em pelo menos uma aresta, por isso, após n − 1 passagens, estão todos encontrados.
Quão rápido é o Bellman–Ford?
Cada passagem verifica todas as E arestas e há no máximo V − 1 passagens, por isso o trabalho cresce com V × E. Isso é mais lento do que o algoritmo de Dijkstra, e é por isso que o Bellman–Ford se usa quando as arestas podem ser negativas.
O meu grafo é enviado para algum lado?
Não. O grafo é criado e percorrido no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor