Algoritmo de Bellman-Ford

O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um digrafo (grafo orientado ou dirigido) 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 $O(V\times E)$ onde V é o número de vértices e E o número de arestas.^[2]^[3]

↑ 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
↑ RFC 1058
↑ [1]

[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]

[1]

[2]

[3]

Algoritmo de Bellman-Ford

From Wikipedia, the free encyclopedia · View on Wikipedia