Bellman–Ford algorithm
The algorithm of Bellman and Ford ( after its inventors Richard Bellman and Lester Ford ) is an algorithm in graph theory and is used to calculate the shortest paths from a start node in an edge-weighted graph. It is sometimes spoken, as well as Edward F. Moore has contributed to its development and the Moore - Bellman - Ford algorithm.
Unlike the Dijkstra algorithm, the most popular method to search for shortest paths in graphs, the weights of the edges may also be negative here. Negative weight cycles that are reachable from the start node, must be excluded, because otherwise they could go through any number of times and thus lower weight paths always be constructed, so there would be no path of least weight. The Bellman - Ford algorithm can detect the presence of cycles negative weight.
Algorithm
G denotes the weighted graph with vertex set V and edge set E. weight to the weight of an edge between two nodes. s is the start node can be calculated starting from which the shortest paths to all other nodes, and n is the number of nodes in V.
If the execution of the algorithm terminates, the output can be removed, if G has a cycle of negative length. If this is not the case, distance to each node contains its distance s, which is the weight of a shortest path starting from S. By previous addition, a spanning tree is defined for storing the shortest paths from s outgoing, in the form of an out - tree. Starting from a node can be in the corresponding shortest path backwards determine by recursively so long visited the node is given by predecessors, until one reaches s.
01 for each v in V 02 Distance (v ): = infinity, predecessor ( v): = no 03 Distance ( s ): = 0 04 repeated n - 1 times 05 for each (u, v) e 06 if distance ( u ) weight (u, v) < distance ( v) 07 then 08 Distance (v ): = distance ( u ) weight (u, v) 09 predecessor ( v): = u 10 for each (u, v) e 11 when distance ( u ) weight ( u, v) < distance ( v) then 12 STOP with output "There is a cycle of negative weight. " 13 output distance In -th pass through the loop ( 04-09 ) - path with maximum edges found or a shorter route with more edge is a shortest to each node. A path without cycles contains at most nodes, ie edges. If in ( 10-12 ), it is determined that a path is not optimal, this a cycle with negative weight must therefore contain.
Complexity
The running time of the algorithm is, the number of nodes and the number of edges in the graph shown.
If you want to find the shortest paths from each node to every other node, so you have the algorithm for each starting node again apply for a total of n times. The runtime complexity for this is thus.
Applications
The Bellman - Ford algorithm finds among other things in the distance vector algorithm, a dynamic routing algorithm, using. This is used, for example, from Routing Information Protocol, are dynamically created within a network administrative domain routing tables ( Interior Gateway Protocol).
Other methods for calculating shortest paths
Faster than the Bellman - Ford algorithm is Dijkstra's algorithm, a greedy algorithm to search the shortest path that receives successively to each next best nodes from a priority queue in a result set S. Its disadvantage, however, is that he accepts as input only graphs with non-negative weights. The A * algorithm expands the Dijkstra's algorithm for a estimator. Another method for searching the shortest path, which, like the Bellman - Ford algorithm is based on dynamic programming, is the Floyd - Warshall algorithm. Both rely their correctness on the optimality principle of Bellman.