|
|
| (581 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| {{Infobox Algorithm
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
| |class=[[Single-source shortest path problem]] (for weighted directed graphs)
| |
| |image=
| |
| |caption =
| |
| |data=[[Graph (data structure)|Graph]]
| |
| |time=<math>O (|V| |E|)</math>
| |
| |space=<math>O (|V|)</math>
| |
| }}
| |
|
| |
|
| {{Tree search algorithm}}
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| The '''Bellman–Ford algorithm''' computes single-source [[shortest path]]s in a [[weighted digraph]].<ref name="Bang">{{Cite book|first=Jørgen |last=Bang-Jensen||coauthors=Gregory Gutin|title=Digraphs: Theory, Algorithms and Applications|edition=First |isbn=978-1-84800-997-4|chapter=Section 2.3.4: The Bellman-Ford-Moore algorithm|url=http://www.cs.rhul.ac.uk/books/dbook/}}</ref>
| | Registered users will be able to choose between the following three rendering modes: |
| For graphs with only non-negative edge weights, the faster [[Dijkstra's algorithm]] also solves the problem.
| |
| Thus, Bellman–Ford is used primarily for graphs with negative edge weights.
| |
| The algorithm is named after its developers, [[Richard Bellman]] and [[L. R. Ford, Jr.|Lester Ford, Jr.]]
| |
|
| |
|
| Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm.<ref>{{Cite book|first=Robert |last=Sedgewick|title= Algorithms in Java|edition= Third |isbn= 0-201-36121-3|chapter=Section 21.7: Negative Edge Weights|url=http://safari.oreilly.com/0201361213/ch21lev1sec7|ref=harv|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}</ref>
| | '''MathML''' |
| However, if a graph contains a "negative cycle", i.e., a [[cycle (graph theory)|cycle]] whose edges sum to a negative value, then [[Walk (graph theory)|walks]] of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a ''shortest'' path.
| | :<math forcemathmode="mathml">E=mc^2</math> |
| In such a case, the Bellman-Ford algorithm can detect negative cycles and report their existence, but it cannot produce a correct "shortest path" answer if a negative cycle is reachable from the source.<ref>Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, New York: Pearson Education, Inc..</ref><ref name="Bang"/>
| |
|
| |
|
| ==Algorithm==
| | <!--'''PNG''' (currently default in production) |
| Bellman–Ford is based on [[dynamic programming]] approach. In its basic structure it is similar to [[Dijkstra's Algorithm]], but instead of [[Greedy algorithm|greedily]] selecting the minimum-weight node not yet processed to relax, it simply relaxes ''all'' the edges, and does this |''V'' | − 1 times, where |''V'' | is the number of vertices in the graph. The repetitions allow minimum distances to propagate accurately throughout the graph, since, in the absence of negative cycles, the shortest path can visit each node at most only once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case.
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| Bellman–Ford runs in ''[[Big O notation|O]]''(|''V''|·|''E''|) time, where |''V''| and |''E''| are the number of vertices and edges respectively.
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| '''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)
| | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
| ''// This implementation takes in a graph, represented as lists of vertices''
| |
| ''// and edges, and modifies the vertices so that their ''distance'' and''
| |
| ''//'' predecessor ''attributes store the shortest paths.''
| |
|
| |
| ''// Step 1: initialize graph''
| |
| '''for each''' vertex v '''in''' vertices:
| |
| '''if''' v '''is''' source '''then''' v.distance := 0
| |
| '''else''' v.distance := '''infinity'''
| |
| v.predecessor := '''null'''
| |
|
| |
| ''// Step 2: relax edges repeatedly''
| |
| '''for''' i '''from''' 1 '''to''' size(vertices)-1:
| |
| '''for each''' edge uv '''in''' edges: ''// uv is the edge from u to v''
| |
| u := uv.source
| |
| v := uv.destination
| |
| '''if''' u.distance + uv.weight < v.distance:
| |
| v.distance := u.distance + uv.weight
| |
| v.predecessor := u
| |
|
| |
| ''// Step 3: check for negative-weight cycles''
| |
| '''for each''' edge uv '''in''' edges:
| |
| u := uv.source
| |
| v := uv.destination
| |
| '''if''' u.distance + uv.weight < v.distance:
| |
| '''error''' "Graph contains a negative-weight cycle"
| |
|
| |
|
| ==Proof of correctness== | | ==Demos== |
|
| |
|
| The correctness of the algorithm can be shown by [[mathematical induction|induction]]. The precise statement shown by induction is:
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
|
| |
|
| '''Lemma'''. After ''i'' repetitions of ''for'' cycle:
| |
| * If Distance(''u'') is not infinity, it is equal to the length of some path from ''s'' to ''u'';
| |
| * If there is a path from ''s'' to ''u'' with at most ''i'' edges, then Distance(u) is at most the length of the shortest path from ''s'' to ''u'' with at most ''i'' edges.
| |
|
| |
|
| '''Proof'''. For the base case of induction, consider <code>i=0</code> and the moment before ''for'' cycle is executed for the first time. Then, for the source vertex, <code>source.distance = 0</code>, which is correct. For other vertices ''u'', <code>u.distance = '''infinity'''</code>, which is also correct because there is no path from ''source'' to ''u'' with 0 edges.
| | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by
| | ==Test pages == |
| <code>v.distance := u.distance + uv.weight</code>. By inductive assumption, <code>u.distance</code> is the length of some path from ''source'' to ''u''. Then <code>u.distance + uv.weight</code> is the length of the path from ''source'' to ''v'' that follows the path from ''source'' to ''u'' and then goes to ''v''.
| |
|
| |
|
| For the second part, consider the shortest path from ''source'' to ''u'' with at most ''i'' edges. Let ''v'' be the last vertex before ''u'' on this path. Then, the part of the path from ''source'' to ''v'' is the shortest path from ''source'' to ''v'' with at most ''i-1'' edges. By inductive assumption, <code>v.distance</code> after ''i''−1 cycles is at most the length of this path. Therefore, <code>uv.weight + v.distance</code> is at most the length of the path from ''s'' to ''u''. In the ''i<sup>th</sup>'' cycle, <code>u.distance</code> gets compared with <code>uv.weight + v.distance</code>, and is set equal to it if <code>uv.weight + v.distance</code> was smaller. Therefore, after ''i'' cycles, <code>u.distance</code> is at most the length of the shortest path from ''source'' to ''u'' that uses at most ''i'' edges.
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices ''v''[0], ..., ''v''[''k''−1],
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| <code>v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight</code>
| | ==Bug reporting== |
| | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| Summing around the cycle, the ''v''[''i''].distance terms and the ''v''[''i''−1 (mod ''k'')] distance terms cancel, leaving
| |
| | |
| <code>0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight</code>
| |
| | |
| I.e., every cycle has nonnegative weight.
| |
| | |
| ==Finding negative cycles== | |
| When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman-Ford algorithm can be used for applications in which this is the target to be sought - for example in [[cycle-cancelling]] techniques in [[Flow network|network flow]] analysis.<ref name="Bang"/>
| |
| | |
| == 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). The algorithm is distributed because it involves a number of nodes (routers) within an [[autonomous system (Internet)|Autonomous system]], a collection of IP networks typically owned by an ISP.
| |
| It consists of the following steps:
| |
| | |
| # Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
| |
| # Each node sends its table to all neighboring nodes.
| |
| # When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.
| |
| | |
| The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:
| |
| | |
| * It does not scale well.
| |
| * Changes in [[network topology]] are not reflected quickly since updates are spread node-by-node.
| |
| * [[Count to infinity#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).
| |
| | |
| ==Yen's improvement==
| |
| {{harvtxt|Yen|1970}} described an improvement to the Bellman–Ford algorithm for a graph without negative-weight cycles. Yen's improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into one of two subsets. The first subset, ''E<sub>f</sub>'', contains all edges (''v<sub>i</sub>'', ''v<sub>j</sub>'') such that ''i'' < ''j''; the second, ''E<sub>b</sub>'', contains edges (''v<sub>i</sub>'', ''v<sub>j</sub>'') such that ''i'' > ''j''. Each vertex is visited in the order ''v<sub>1</sub>'', ''v<sub>2</sub>'', ..., ''v''<sub>|''V''|</sub>, relaxing each outgoing edge from that vertex in ''E<sub>f</sub>''. Each vertex is then visited in the order ''v''<sub>|''V''|</sub>, ''v''<sub>|''V''|−1</sub>, ..., ''v''<sub>1</sub>, relaxing each outgoing edge from that vertex in ''E<sub>b</sub>''. Yen's improvement effectively halves the number of "passes" required for the single-source-shortest-path solution.
| |
| | |
| ==Notes==
| |
| {{Reflist}}
| |
| | |
| ==References==
| |
| *{{cite journal
| |
| | last = Bellman | first = Richard | authorlink = Richard Bellman
| |
| | mr = 0102435
| |
| | journal = Quarterly of Applied Mathematics
| |
| | pages = 87–90
| |
| | title = On a routing problem
| |
| | volume = 16
| |
| | year = 1958
| |
| | ref = harv}}.
| |
| *{{cite book|author1-link=L. R. Ford, Jr.|last1=Ford|first1=L. R., Jr.|author2-link=D. R. Fulkerson|last2=Fulkerson|first2=D. R.|title=Flows in Networks|publisher=Princeton University Press|year=1962}}.
| |
| *{{Introduction to Algorithms}}, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman–Ford algorithm, pp. 588–592. Problem 24-1, pp. 614–615.
| |
| *{{Introduction to Algorithms}}, Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Section 24.1: The Bellman–Ford algorithm, pp. 651–655.
| |
| *{{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 journal
| |
| | last = Yen | first = Jin Y.
| |
| | mr = 0253822
| |
| | journal = Quarterly of Applied Mathematics
| |
| | pages = 526–530
| |
| | title = An algorithm for finding shortest routes from all source nodes to a given destination in general networks
| |
| | volume = 27
| |
| | year = 1970
| |
| | ref = harv}}.
| |
| | |
| ==External links==
| |
| * [http://snippets.dzone.com/posts/show/4828 C code example]
| |
| * [http://code.google.com/p/annas/ Open Source Java Graph package with Bellman-Ford Algorithms]
| |
| * [http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/ C++ implementation of Yen's Algorithm (Microsoft Visual Studio project)]
| |
| | |
| [[Category:Graph algorithms]]
| |
| [[Category:Polynomial-time problems]]
| |
| [[Category:Articles with example C code]]
| |
| [[Category:Articles with example pseudocode]]
| |
| | |
| [[ca:Algorisme de Bellman-Ford]]
| |
| [[cs:Bellmanův-Fordův algoritmus]]
| |
| [[de:Bellman-Ford-Algorithmus]]
| |
| [[es:Algoritmo de Bellman-Ford]]
| |
| [[fa:الگوریتم بلمن–فورد]]
| |
| [[fr:Algorithme de Bellman-Ford]]
| |
| [[ko:벨만-포드 알고리즘]]
| |
| [[it:Algoritmo di Bellman-Ford]]
| |
| [[he:אלגוריתם בלמן-פורד]]
| |
| [[ka:ბელმან-ფორდის ალგორითმი]]
| |
| [[lv:Bellmana-Forda algoritms]]
| |
| [[nl:Algoritme van Bellman-Ford]]
| |
| [[ja:ベルマン-フォード法]]
| |
| [[pl:Algorytm Bellmana-Forda]]
| |
| [[pt:Algoritmo de Bellman-Ford]]
| |
| [[ru:Алгоритм Беллмана — Форда]]
| |
| [[th:ขั้นตอนวิธีของเบลแมน-ฟอร์ด]]
| |
| [[uk:Алгоритм Беллмана—Форда]]
| |
| [[vi:Thuật toán Bellman-Ford]]
| |
| [[zh:贝尔曼-福特算法]]
| |
