Main Page

2014-08-10T17:39:44Z

AaliyahT21:

{{Infobox Algorithm
|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}}

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>
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={{inconsistent citations}}}}</ref>
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.
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==
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.

Bellman–Ford runs in ''[[Big O notation|O]]''(|''V''|·|''E''|) time, where |''V''| and |''E''| are the number of vertices and edges respectively.

'''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)
''// 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==

The correctness of the algorithm can be shown by [[mathematical induction|induction]]. The precise statement shown by induction is:

'''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.

For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by
<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 ''ith'' 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.

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],

<code>v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight</code>

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, ''Ef'', contains all edges (''vi'', ''vj'') such that ''i'' < ''j''; the second, ''Eb'', contains edges (''vi'', ''vj'') such that ''i'' > ''j''. Each vertex is visited in the order ''v1'', ''v2'', ..., ''v''|''V''|, relaxing each outgoing edge from that vertex in ''Ef''. Each vertex is then visited in the order ''v''|''V''|, ''v''|''V''|−1, ..., ''v''1, relaxing each outgoing edge from that vertex in ''Eb''. 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:贝尔曼-福特算法]]

formulasearchengine - User contributions [en]

Main Page