Bellman-Ford algorithm

The algorithm by Bellman and Ford (after its inventors Richard Bellman and Lester Ford ) is an algorithm of graph theory and is used to calculate the shortest paths starting from a starting node in an edge-weighted graph . Occasionally the Moore-Bellman-Ford algorithm is also used, as Edward F. Moore also contributed to its development.

In contrast to Dijkstra's algorithm , the best-known method for searching for the shortest paths in graphs , the weights of the edges can also be negative here . Cycles of negative weight, which can be reached from the starting node, must be excluded, because otherwise these could run through as often as desired and thus paths of ever lower weight could be constructed, so there would be no path with the lowest weight at all. The Bellman-Ford algorithm can detect the presence of cycles of negative weight.

description

${\displaystyle G}$denotes the weighted graph with the node set and the edge set . Weight indicates the weight of an edge between two nodes. is the starting node from which the shortest paths to all other nodes are calculated, and is the number of nodes in . ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle V}$

When the algorithm finishes executing, the output can be used to determine whether a cycle is of negative length. If this is not the case, Distance for each node contains its distance to , i.e. the weight of a shortest path starting from it. A spanning tree is also defined by predecessors , which saves the shortest possible outgoing routes in the form of an out tree . Starting from a node, you can determine the corresponding shortest path backwards by recursively visiting the node given by the predecessor until you have reached. ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$

01  für jedes v aus V
02      Distanz(v) := unendlich, Vorgänger(v) := keiner
03  Distanz(s) := 0

04  wiederhole n − 1 mal
05      für jedes (u,v) aus E
06          wenn (Distanz(u) + Gewicht(u,v)) < Distanz(v) dann
07              Distanz(v) := Distanz(u) + Gewicht(u,v)
08              Vorgänger(v) := u

09  für jedes (u,v) aus E
10      wenn (Distanz(u) + Gewicht(u,v)) < Distanz(v) dann
11          STOPP mit Ausgabe „Es gibt einen Zyklus negativen Gewichtes.“

12  Ausgabe Distanz, Vorgänger

In the -th iteration of the loop in lines 04 to 08, a shortest path from the starting node to the node with a maximum of edges or a shorter path with more edges is found for each node . A path without cycles contains at most nodes, i.e. edges. If it is found in line 10 that a path is not optimal, it must consequently contain a cycle with negative weight. ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Proof of correctness

The correctness of the algorithm can be shown by complete induction .

After running through the loop in lines 04 to 08: ${\displaystyle i}$

• If not infinite, it is equal to the length of a path from to . ${\displaystyle Distanz(u)}$ ${\displaystyle s}$ ${\displaystyle u}$
• If there is a path from to with at most edges , at most is equal to the length of the shortest path from to with at most edges. ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle i}$ ${\displaystyle Distanz(u)}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle i}$

Consider for the start of induction and the moment before the loop is executed for the first time. Then what is correct applies to the start node . For other node is , which is also correct, because there is no path of according with 0 edges are. ${\displaystyle i=0}$ ${\displaystyle Distanz(s)=0}$ ${\displaystyle v}$ ${\displaystyle Distanz(v)=\infty }$ ${\displaystyle s}$ ${\displaystyle v}$

For the inductive case we first prove the first part. Consider the step where the removal of a node is updated by. According to the induction hypothesis , the length of a path is from to . Then the length of the path from to that follows the path from to and then goes to. ${\displaystyle Distanz(v):=Distanz(u)+Gewicht(u,v)}$ ${\displaystyle Distanz(u)}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle Distanz(u)+Gewicht(u,v)}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle v}$

For the second part, consider a shortest path (there can be more than one) from to with at most edges . Be the last node before on this path . Then the part of the path from to is a shortest path from to with at most edges, because if it weren't, there would have to be a shorter path from to with at most edges, and we could then append the edge to that path to get one To get a path from to with at most edges that is shorter than - a contradiction. According to the induction hypothesis , after iterations is at most equal to the length of this path from to . Therefore is at most equal to the length of . In the run , it is compared with and set to this value if is smaller. Therefore after iterations is at most equal to the length of , ie the length of the shortest path from to , which contains at most edges. ${\displaystyle P}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle i-1}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle i-1}$ ${\displaystyle (u,v)}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle P}$ ${\displaystyle Distanz(u)}$ ${\displaystyle i-1}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle Distanz(u)+Gewicht(u,v)}$ ${\displaystyle P}$ ${\displaystyle i}$ ${\displaystyle Distanz(v)}$ ${\displaystyle Distanz(u)+Gewicht(u,v)}$ ${\displaystyle Distanz(u)+Gewicht(u,v)}$ ${\displaystyle i}$ ${\displaystyle Distanz(v)}$ ${\displaystyle P}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle i}$

If there are no cycles are negative weight, each of the shortest path each node at most once, so to 11 no further improvements can be made in line 09th Conversely, suppose that no improvement can be made. Then the following applies for each cycle with the nodes : ${\displaystyle v_{0},\ldots ,v_{k-1}}$

${\displaystyle Distanz(v_{i})\leq Distanz(v_{i-1\mod k})+Gewicht(v_{i-1\mod k},v_{i})}$

Summed up over the cycle , the expressions and cancel each other out and we get: ${\displaystyle Distanz(v_{i})}$ ${\displaystyle Distanz(v_{i-1\mod k})}$

${\displaystyle 0\leq \sum _{i=1}^{k}Gewicht(v_{i-1\mod k},v_{i})}$

That is, each cycle has a nonnegative weight.

Time complexity

The running time of the Bellman-Ford algorithm is in , where are the number of nodes and the number of edges in the graph. ${\displaystyle {\mathcal {O}}(n\cdot m)}$ ${\displaystyle n}$ ${\displaystyle m}$

If you want to find the shortest paths from every node to every other node, you have to apply the algorithm once for each starting node, i.e. a total of times. The runtime complexity for this is consequently . ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(n^{2}\cdot m)}$

Comparison with other algorithms

Faster than the Bellman-Ford algorithm is Dijkstra's algorithm , a greedy algorithm to search the shortest path which successively the respective nearest node of a priority queue in a result set S receives. It has a term of . Its disadvantage, however, is that it only allows graphs with nonnegative weights as input. ${\displaystyle {\mathcal {O}}(n\cdot \log(n)+m)}$

The A * algorithm extends the Dijkstra algorithm by an estimation function and has the running time . ${\displaystyle {\mathcal {O}}(n^{2})}$

Another method for finding the shortest paths, which, like the Bellman-Ford algorithm, is based on dynamic programming , is the Floyd-Warshall algorithm . Both base their correctness on Bellman's principle of optimality .

Applications

The Bellman-Ford algorithm is used, among other things, in the distance vector algorithm , a dynamic routing algorithm . This is z. B. from the Routing Information Protocol used with the routing tables within an administrative network - domain are created dynamically ( Interior Gateway Protocol ).

A distributed variant of the Bellman-Ford algorithm is used in distance vector routing protocols, such as the Routing Information Protocol . The algorithm is distributed, because it provides a number of nodes (routers) within an autonomous system comprises a collection of IP - networks , and are generally a Internet Service Provider belong. It consists of the following steps:

• Each node calculates the distances between itself and all other nodes within the autonomous system and saves 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 paths to all other nodes and updates its own table to reflect any changes.

The main disadvantages of the Bellman-Ford algorithm in this environment are as follows:

• It doesn't scale well.
• Changes in the network topology are not reflected quickly because updates are distributed node by node.
• It counts to infinity if connection or node errors make a node inaccessible from a number of other nodes. These nodes may spend forever incrementally increasing their estimates of the distances to it, and routing loops may occur in the meantime.

software

The algorithm is in the free Python - Library NetworkX implemented. Example:

import networkx as nx
G = nx.Graph()
e = [('a', 'b', 3), ('b', 'c', 9), ('a', 'c', 5), ('c', 'd', 12)]
G.add_weighted_edges_from(e)
print(nx.bellman_ford_path(G, 'a', 'd'))
print(nx.bellman_ford_path_length(G, 'a', 'd'))

In the example above, a graph is defined with nodes a, b, c and d. Edges with weights 3, 9, 5 and 12 exist between nodes ab, bc, ac and cd. The Bellman-Ford algorithm is then executed on the graph in order to find the shortest route between nodes a and d. The result is therefore the distance acd. Then the minimum length between nodes a and d is calculated, which results in 5 + 12 = 17.

literature

• LR Ford: Network flow theory, Paper P-923. The Rand Corporation, Santa Monica 1956
• RE Bellman: On a Routing Problem. In: Quarterly of Applied Mathematics. 16 (1) / 1958. Brown University, pp. 87-90, ISSN  0033-569X
• EF Moore: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching. 2/1959. Harvard University Press, pp. 285-292
• LR Ford, DR Fulkerson: Flows in Networks. , Princeton University Press, Princeton 1962, ISBN 0-691-07962-5
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithms - An Introduction . 2nd Edition. Oldenbourg Wissenschaftsverlag, Munich 2007, ISBN 978-3-486-58262-8 , chapters 24 and 25.

Web links

• An interactive applet for learning, trying out and demonstrating the algorithm

Individual evidence

1. ↑ Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - An Introduction . 2nd Edition. Oldenbourg Wissenschaftsverlag, Munich 2007, ISBN 978-3-486-58262-8 , p. 585-586 .
2. ^ Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Retrieved October 24, 2018 .