Editing Bellman–Ford algorithm (section)

{{Short description|Algorithm for finding the shortest paths in graphs}}
{{Infobox Algorithm
|class=[[Single-source shortest path problem]] (for weighted directed graphs)
|image= Bellman–Ford algorithm example.gif
|caption = 
|data=[[Graph (data structure)|Graph]]
|time=<math>\Theta (|V| |E|)</math>
|best-time=<math>\Theta (|E|)</math>
|space=<math>\Theta (|V|)</math>
}}

The '''Bellman–Ford algorithm''' is an [[algorithm]] that computes [[shortest path]]s from a single source [[vertex (graph theory)|vertex]] to all of the other vertices in a [[weighted digraph]].<ref name=Bang>{{harvtxt|Bang-Jensen|Gutin|2000}}</ref>
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.<ref name="web.stanford.edu">[https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf Lecture 14] stanford.edu</ref> The algorithm was first proposed by {{harvs|first=Alfonso|last=Shimbel|year=1955|txt}}, but is instead named after [[Richard Bellman]] and [[L. R. Ford Jr.|Lester Ford Jr.]], who published it in [[#{{harvid|Bellman|1958}}|1958]] and [[#{{harvid|Ford|1956}}|1956]], respectively.<ref name="Schrijver">{{harvtxt|Schrijver|2005}}</ref> [[Edward F. Moore]] also published a variation of the algorithm in [[#{{harvid|Moore|1959}}|1959]], and for this reason it is also sometimes called the '''Bellman–Ford–Moore algorithm'''.<ref name=Bang />

Negative edge weights are found in various applications of graphs. This is why this algorithm is useful.{{sfnp|Sedgewick|2002}}
If a graph contains a "negative cycle" (i.e. a [[cycle (graph theory)|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 (graph theory)|walk]] around the negative cycle. In such a case, the Bellman–Ford algorithm can detect and report the negative cycle.<ref name=Bang />{{sfnp|Kleinberg|Tardos|2006}}