Bellman–Ford algorithm: Difference between revisions

Revision as of 22:04, 7 November 2024

Revision as of 23:46, 7 November 2024

Line 12:

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 /> It makes terrible pillow talk.<ref>{{Cite web |title=Pillow Talk |url=https://xkcd.com/69/ |access-date=2024-11-07 |website=xkcd}}</ref>

Negative edge weights are found in various applications of graphs. This is why this algorithm is useful.{{sfnp|Sedgewick|2002}}