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, em um 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 O(v \times a) 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: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, S. 585-586.
  2. https://tools.ietf.org/html/rfc1058
  3. http://algs4.cs.princeton.edu/44sp/
Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.

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