Bellman - Ford Algorithm

The history of the algorithm is connected immediately with three independent mathematicians: Lester Ford, Richard Bellman and Edward Moore. Ford and Bellman published the algorithm in 1956 and 1958, respectively, and Moore did it in 1957. And sometimes it is called the Bellman-Ford-Moore algorithm. The method is used in some distance vector routing protocols, for example, in RIP (Routing Information Protocol).

Like the Dijkstra algorithm, the Bellman-Ford algorithm calculates the shortest paths from one vertex to all others in a weighted graph. It is suitable for working with graphs that have negative weight edges. But the range of applicability of the algorithm affects not all such graphs, since each successive passage along the path made up of edges, the sum of the weights of which is negative (i.e., by a negative cycle), only improves the required value. An infinite number of improvements makes it impossible to determine one particular value that is optimal. In this regard, the Bellman-Ford algorithm is not applicable to graphs with negative cycles, but it allows one to determine the presence of such, as will be discussed later.

To solve the problem, that is, to find all the shortest paths from the vertex s to all the others, using the Bellman – Ford algorithm, this means using the dynamic programming method: break it into typical subtasks, find the solution last, thereby ending the main task. Here the solution to each of these subtasks is to determine the best path from one individual edge to any other. To store the results of the algorithm, we will create a one-dimensional d [] array. In each of its i-th element, the value of the shortest path from the vertex s to the vertex i (if any) will be stored. Initially, we assign the d [] elements to the array values ​​equal to conditional infinity (for example, the number of obviously larger sums of all weights), and we write zero to the d [s] element. So we used known and necessary information, namely, it is known that the best path from the vertex s to itself is 0, and it must be assumed that other vertices from s are unavailable. As the algorithm runs, for some of them, this condition will turn out to be false, and the optimal cost of the paths to these vertices from s will be calculated.

Given the graph G = (V, E), n = | V |, and m = | E |. Denote the adjacent vertices of this graph by the symbols v and u (vÎV and uÎV), and the weight of the edge (v, u) by the symbol w. In other words, the weight of an edge going out of a vertex v and entering a vertex u will be equal to w. Then the key part of the Bellman-Ford algorithm will take the following form:

For i from 1 to n-1 perform
For j from 1 to m perform
If d [v] + w (v, u) d [u]

At each nth step, attempts are made to improve the values ​​of the elements of the array d []: if the sum composed of the weight of the edge w (v, u) and the weight stored in the element d [v] is less than the weight d [u], then it is assigned to the last .

C ++ program code:

Pascal program code:

Here the graph is represented by a simplified list of edges, which is formed as the user enters the weights matrix. The main part of the Bellman-Ford algorithm (condition check) is performed m * (n-1) times, since the number of repetitions of the outer loop is n-1, and the inner one is m. Rejecting the nth iteration is advisable, since the algorithm does its job in an n-1 step, but starting the external loop n times will reveal the presence of a negative loop in the graph. This can be checked, for example, with the following modification:

Here, the outer loop is executed n times (in C ++ it is customary to specify the initial value 0, therefore, for a given code n-1 times), and if improvement will be possible at the n-th stage, this indicates the presence of a negative cycle.