Bellman–Ford algorithm: Difference between revisions

Revision as of 10:05, 7 April 2024

Latest revision as of 02:40, 25 August 2025

(33 intermediate revisions by 17 users not shown)

Line 1:

{{merge from|Shortest path faster algorithm|discuss=Talk:Bellman–Ford_algorithm#Proposed_Merger:_SPFA_into_Optimizations|date=April 2024}}

{{Short description|Algorithm for finding the shortest paths in graphs}}

{{Infobox Algorithm

Line 18 ⟶ 17:

== Algorithm ==

{{Unreferenced section|date=December 2021}}

[[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 (approximationiterative method)|relaxation]], in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path.{{sfnp|Cormen|Leiserson|Rivest|Stein|2022|loc=Section 22.1}}

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 answerdistances remainsremain the same.{{sfnp|Cormen|Leiserson|Rivest|Stein|2022|loc=Section 22.1}}

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 32 ⟶ 30:

''// This implementation takes in a graph, represented as''

''// lists of vertices (represented as integers [0..n-1]) and edges,''

''// edges, and fills two arrays (distance and predecessor) holding''

''// holding the shortest path from the source to each vertex''

distance := ''list'' of size ''n''

Line 46 ⟶ 44:

predecessor[v] := '''null'''

// The distance from the source to itself is, of course, zero

distance[source] := 0

Line 60 ⟶ 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 66 ⟶ 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 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 booleanBoolean array (<code>visited</code>) to find a vertex on the cycle, but any [[Cycle detection|cycle finding]] algorithm can be used to find a vertex on the cycle.

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>

{{Unreferenced section|date=March 2019}}

The correctness of the algorithm can be shown by [[mathematical induction|induction]]:<ref name="web.stanford.edu"/>

'''Lemma'''. After ''i'' repetitions of ''for'' loop,

Line 114 ⟶ 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 130 ⟶ 128:

The Bellman–Ford algorithm may be improved in practice (although not in the worst case) by the observation that, if an iteration of the main loop of the algorithm terminates without making any changes, the algorithm can be immediately terminated, as subsequent iterations will not make any more changes. With this early termination condition, the main loop may in some cases use many fewer than {{math|{{abs|''V''}}&nbsp;−&nbsp;1}} iterations, even though the worst case of the algorithm remains unchanged. The following improvements all maintain the <math>O(|V|\cdot |E|)</math> worst-case time complexity.

A variation of the Bellman–Ford algorithm known as [[Shortest Path Faster Algorithm]], first described by {{harvtxt|Moore|1959}}, reduces the number of relaxation steps that need to be performed within each iteration of the algorithm. If a vertex ''v'' has a distance value that has not changed since the last time the edges out of ''v'' were relaxed, then there is no need to relax the edges out of ''v'' a second time. In this way, as the number of vertices with correct distance values grows, the number whose outgoing edges that need to be relaxed in each iteration shrinks, leading to a constant-factor savings in time for [[dense graph]]s. This variation can be implemented by keeping a collection of vertices whose outgoing edges need to be relaxed, removing a vertex from this collection when its edges are relaxed, and adding to the collection any vertex whose distance value is changed by a relaxation step. In China, this algorithm was popularized by Fanding Duan, who rediscovered it in 1994, as the "shortest path faster algorithm".<ref>{{cite journal|last=Duan|first=Fanding|year=1994|title=关于最短路径的SPFA快速算法 [About the SPFA algorithm]|journal=Journal of Southwest Jiaotong University|volume=29|issue=2|pages=207–212|url=http://wenku.baidu.com/view/3b8c5d778e9951e79a892705.html}}</ref>

{{harvtxt|Yen|1970}} described another improvement to the Bellman–Ford algorithm. His improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into two subsets. The first subset, ''E_f'', contains all edges (''v_i'', ''v_j'') such that ''i'' < ''j''; the second, ''E_b'', contains edges (''v_i'', ''v_j'') such that ''i'' > ''j''. Each vertex is visited in the order {{math|''v₁'', ''v₂'', ..., ''v''_{{{!}}''V''{{!}}}}}, relaxing each outgoing edge from that vertex in ''E_f''. Each vertex is then visited in the order {{math|''v''_{{{!}}''V''{{!}}}, ''v''_{{{!}}''V''{{!}}−1}, ..., ''v''₁}}, relaxing each outgoing edge from that vertex in ''E_b''. Each iteration of the main loop of the algorithm, after the first one, adds at least two edges to the set of edges whose relaxed distances match the correct shortest path distances: one from ''E_f'' and one from ''E_b''. This modification reduces the worst-case number of iterations of the main loop of the algorithm from {{math|{{abs|''V''}}&nbsp;−&nbsp;1}} to <math>|V|/2</math>.<ref>Cormen et al., 2nd4th ed., Problem 2422-1, ppp. 614–615640.</ref><ref name=Sedweb />

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_f'' and ''E_b'') 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|titlecontribution=Randomized speedup of the Bellman–Ford algorithm|first1=M. J.|last1=Bannister|first2=D.|last2=Eppstein|author2-link=David Eppstein|arxiv=1111.5414|conferencetitle=Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan|year=2012|pages=41–47|doi=10.1137/1.9781611973020.6}}

*{{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}}, Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7edition=4}}. Section 2422.1: The Bellman–Ford algorithm, pp.&nbsp;588–592612–616. Problem 24–122–1, pp.&nbsp;614–615. Third Edition. MIT Press, 2009. {{ISBN|978-0-262-53305-8}}. Section 24.1: The Bellman–Ford algorithm, ppp.&nbsp;651–655640.

*{{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}}