algoritmo de Bellman-Ford
Sign in to saveAlso known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm
algorithm for finding single-source shortest paths in graphs, allowing some edge weights to be negative
Key facts
- Class
- Single-source shortest path problem (for weighted directed graphs)
- Data structure
- Graph
- Worst case performance
- Θ ( | V | | E | ) {\displaystyle \Theta (|V||E|)}
- Best case performance
- Θ ( | E | ) {\displaystyle \Theta (|E|)}
- Worst case space complexity
- Θ ( | V | ) {\displaystyle \Theta (|V|)}
via Wikipedia infobox
Wikidata facts
- Named after
- L. R. Ford, Jr.
- Image
- Bellman–Ford algorithm example.gif
Show 5 more facts
- discoverer or inventor
- Edward F. Moore
- derivative work
- Babel
- Commons category
- Bellman–Ford algorithm
Sources (2)
via Wikidata · CC0
Article · Português
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. O algoritmo de Bellman-Ford executa em tempo onde V é o número de vértices e E o número de arestas.
Abstract from DBpedia / Wikipedia · CC BY-SA