Bellman–Ford algorithm: Difference between revisions

Revision as of 21:38, 15 January 2024

Revision as of 21:40, 15 January 2024

Line 11:

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>https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf</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 />

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, hence the usefulness of this algorithm.{{sfnp|Sedgewick|2002}}