![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Bellman%25E2%2580%2593Ford_algorithm_example.gif/640px-Bellman%25E2%2580%2593Ford_algorithm_example.gif&w=640&q=50)
Bellman–Ford algorithm
Algorithm for finding the shortest paths in graphs / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Bellman–Ford algorithm?
Summarize this article for a 10 year old
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.[1] It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.[2] The algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively.[3] Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.[1]
![]() | |
Class | Single-source shortest path problem (for weighted directed graphs) |
---|---|
Data structure | Graph |
Worst-case performance | |
Best-case performance | |
Worst-case space complexity |
Negative edge weights are found in various applications of graphs. This is why this algorithm is useful.[4] If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect and report the negative cycle.[1][5]