Content deleted Content added
rm merge banner |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (27 intermediate revisions by 15 users not shown) | |||
Line 17:
== Algorithm ==
[[File:Bellman-Ford worst-case example.svg|thumb|In this example graph, assuming that A is the source and edges are processed in the worst order, from right to left, it requires the full {{math||''V''|−1}} or 4 iterations for the distance estimates to converge. Conversely, if the edges are processed in the best order, from left to right, the algorithm converges in a single iteration.]]
Like [[Dijkstra's algorithm]], Bellman–Ford proceeds by [[Relaxation (
However, Dijkstra's algorithm uses a [[priority queue]] to [[Greedy algorithm|greedily]] select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes ''all'' the edges, and does this <math>|V|-1</math> times, where <math>|V|</math> is the number of vertices in the graph.{{sfnp|Cormen|Leiserson|Rivest|Stein|2022|loc=Section 22.1}}
In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra's algorithm. The intermediate answers and the choices among equally short paths depend on the order of edges relaxed, but the final
Bellman–Ford runs in <math>O(|V|\cdot |E|)</math> [[Big O notation|time]], where <math>|V|</math> and <math>|E|</math> are the number of vertices and edges respectively.
Line 31 ⟶ 30:
''// This implementation takes in a graph, represented as''
''// lists of vertices (represented as integers [0..n-1]) and
''// edges, and fills two arrays (distance and predecessor)
''// holding the shortest path from the source to each vertex''
distance := ''list'' of size ''n''
Line 45 ⟶ 44:
predecessor[v] := '''null'''
// The distance from the source to itself is
distance[source] := 0
Line 59 ⟶ 58:
'''if''' distance[u] + w < distance[v] '''then'''
predecessor[v] := u
''// A negative cycle exists;''
''// find a vertex on the cycle visited := ''list'' of size ''n'' initialized with '''false'''
visited[v] := '''true'''
Line 65:
visited[u] := '''true'''
u := predecessor[u]
''// u is a vertex in a negative cycle,''
''// find the cycle itself'' ncycle := [u]
v := predecessor[u]
Line 80 ⟶ 81:
Since the longest possible path without a cycle can be <math>|V|-1</math> edges, the edges must be scanned <math>|V|-1</math> times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length <math>|V|</math> edges has been found which can only occur if at least one negative cycle exists in the graph.
The edge (u, v) that is found in step 3 must be reachable from a negative cycle, but it isn't necessarily part of the cycle itself, which is why it's necessary to follow the path of predecessors backwards until a cycle is detected. The above pseudo-code uses a
A common improvement when implementing the algorithm is to return early when an iteration of step 2 fails to relax any edges, which implies all shortest paths have been found, and therefore there are no negative cycles. In that case, the complexity of the algorithm is reduced from <math>O(|V|\cdot |E|)</math> to <math>O(l \cdot |E|)</math> where <math>l</math> is the maximum length of a shortest path in the graph.
== Proof of correctness ==
The correctness of the algorithm can be shown by [[mathematical induction|induction]]:<ref name="web.stanford.edu"/><ref>{{Cite journal |last=Dinitz |first=Yefim |last2=Itzhak |first2=Rotem |date=2017-01-01 |title=Hybrid Bellman–Ford–Dijkstra algorithm |url=https://www.sciencedirect.com/science/article/pii/S1570866717300011 |journal=Journal of Discrete Algorithms |volume=42 |pages=35–44 |doi=10.1016/j.jda.2017.01.001 |issn=1570-8667|url-access=subscription }}</ref>
'''Lemma'''. After ''i'' repetitions of ''for'' loop,
Line 113:
== Applications in routing ==
A distributed variant of the Bellman–Ford algorithm is used in [[distance-vector routing protocol]]s, for example the [[Routing Information Protocol]] (RIP).<ref>{{Cite report |url=https://www.rfc-editor.org/rfc/rfc2453 |title=RIP Version 2 |last=Malkin |first=Gary S. |date=November 1998 |publisher=Internet Engineering Task Force |issue=RFC 2453}}</ref> The algorithm is distributed because it involves a number of nodes (routers) within an [[autonomous system (Internet)|Autonomous system (AS)]], a collection of IP networks typically owned by an ISP.▼
▲A distributed variant of the Bellman–Ford algorithm is used in [[distance-vector routing protocol]]s, for example the [[Routing Information Protocol]] (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an [[autonomous system (Internet)|Autonomous system (AS)]], a collection of IP networks typically owned by an ISP.
It consists of the following steps:
Line 125 ⟶ 124:
* Changes in [[network topology]] are not reflected quickly since updates are spread node-by-node.
* [[Distance-vector routing protocol#Count to infinity problem|Count to infinity]] if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops.
== Improvements ==
Line 135 ⟶ 133:
Another improvement, by {{harvtxt|Bannister|Eppstein|2012}}, replaces the arbitrary linear order of the vertices used in Yen's second improvement by a [[random permutation]]. This change makes the worst case for Yen's improvement (in which the edges of a shortest path strictly alternate between the two subsets ''E<sub>f</sub>'' and ''E<sub>b</sub>'') very unlikely to happen. With a randomly permuted vertex ordering, the [[expected value|expected]] number of iterations needed in the main loop is at most <math>|V|/3</math>.<ref name=Sedweb>See Sedgewick's [http://algs4.cs.princeton.edu/44sp/ web exercises] for ''Algorithms'', 4th ed., exercises 5 and 12 (retrieved 2013-01-30).</ref>
{{harvtxt|Fineman|2024}}, at [[Georgetown University]], created an improved algorithm that with high probability runs in <math>\tilde O(|V|^\frac{8}{9}\cdot |E|)</math> [[time complexity|time]]. Here, the <math>\tilde O</math> is a variant of [[big O notation]] that hides logarithmic factors.
== Notes ==
Line 189:
| doi-access = free
}}
*{{cite conference|
*{{cite conference
| last = Fineman | first = Jeremy T.
| editor1-last = Mohar | editor1-first = Bojan
| editor2-last = Shinkar | editor2-first = Igor
| editor3-last = O'Donnell | editor3-first = Ryan
| arxiv = 2311.02520
| contribution = Single-source shortest paths with negative real weights in <math>\tilde O(mn^{8/9})</math> time
| doi = 10.1145/3618260.3649614
| pages = 3–14
| publisher = Association for Computing Machinery
| title = Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024
| year = 2024}}
=== Secondary sources ===
Line 202 ⟶ 214:
*{{Cite book|first1=Jørgen |last1=Bang-Jensen|first2=Gregory|last2=Gutin|year=2000|title=Digraphs: Theory, Algorithms and Applications|edition=First |isbn=978-1-84800-997-4|chapter=Section 2.3.4: The Bellman-Ford-Moore algorithm|publisher=Springer |url=http://www.cs.rhul.ac.uk/books/dbook/}}
*{{cite journal|first=Alexander|last=Schrijver|title=On the history of combinatorial optimization (till 1960)|pages=1–68|publisher=Elsevier|journal=Handbook of Discrete Optimization|year=2005|url=http://homepages.cwi.nl/~lex/files/histco.pdf}}
*{{sfn whitelist|CITEREFCormenLeisersonRivestStein2022}}{{Introduction to Algorithms
*{{cite book | first1 = George T. | last1 = Heineman | first2 = Gary | last2 = Pollice | first3 = Stanley | last3 = Selkow | title= Algorithms in a Nutshell | publisher=[[O'Reilly Media]] | year=2008 | chapter=Chapter 6: Graph Algorithms | pages = 160–164 | isbn=978-0-596-51624-6 }}
*{{cite book|last1=Kleinberg|first1=Jon|author1-link=Jon Kleinberg|last2=Tardos|first2=Éva|author2-link=Éva Tardos|year=2006|title=Algorithm Design|___location=New York|publisher=Pearson Education, Inc.}}
*{{Cite book|first=Robert|last=Sedgewick|author-link=Robert Sedgewick (computer scientist)|year=2002|title=Algorithms in Java|edition=3rd|isbn=0-201-36121-3|chapter=Section 21.7: Negative Edge Weights|publisher=Addison-Wesley |url=http://safari.oreilly.com/0201361213/ch21lev1sec7|access-date=2007-05-28|archive-url=https://web.archive.org/web/20080531142256/http://safari.oreilly.com/0201361213/ch21lev1sec7|archive-date=2008-05-31|url-status=dead}}
{{Graph traversal algorithms}}
| |||