Algoritmo de Bellman-Ford

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um dígrafo ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, num tempo menor, porém exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de Bellman-Ford é normalmente usado apenas quando existem arestas de peso negativo.[1]

O algoritmo de Bellman-Ford executa em tempo onde v é o número de vértices e a o número de arestas.[2][3]

Ver também[editar | editar código-fonte]

Referências

  1. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein (2007). Algorithmen – Eine Einführung 2. ed. München: Oldenbourg Wissenschaftsverlag. pp. 585–586. ISBN 978-3-486-58262-8 
  2. RFC 1058
  3. [1]

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.