Ford-Bellman algorithm
Let's be given a directed weighted graph G with n vertices and m edges, and some starting vertex v . It is required to find the lengths of the shortest paths from the vertex v to all other vertices.
Like Dijkstra, Ford-Bellman looks for the distance from vertex 1 to all others, but works with negative edges< /strong>.
The Ford-Bellman algorithm itself consists of several phases ( n-1). At each phase, all the edges of the graph are examined, and the algorithm tries to relax along each edge (a, b) of the cost c. Relaxation along an edge — this is an attempt to improve the meaning of d[a] the value d[b] + c. In fact, this means that we are trying to improve the answer for the vertex by using the edge and the current answer for the top.
The d array is an array of the shortest lengths from the starting vertex, just like in Dijkstra, we initially fill it with as large numbers as possible, except for the starting vertex, in which you need to put 0.
To store edges, not an adjacency matrix or a weight matrix is used, but a list that indicates from which node the edge leaves ( from), to which it comes ( to) and its weight ( cost).
struct edge {
int from, to, cost;
};
vector<edge> edges;
The INF constant denotes the number "infinity" - it must be chosen in such a way that it obviously exceeds all possible path lengths.
The simplest implementation of the algorithm:
d[v] = 0;
for (int i=0; i<n-1; ++i)
for (int j=0; j<m; ++j)
if (d[edges[j].from] <INF)
d[edges[j].to] = min(d[edges[j].to], d[edges[j].from] + edges[j].cost);
or a little shorter using the syntax C++11:
d[v] = 0;
for (int i=0; i< n-1; ++i)
for (edge j: edges)
if (d[j.from] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.cost);
Work example
Take a simple directed graph with 5 nodes, 4 edges with weight equal to 1.
Let's introduce a list of edges in that order.
4 5 1
3 4 1
2 3 1
1 2 1
Initial values in array of shortest lengths:
where inf should be a matched integer that is always greater than the weight of the edge.
After 1st pass
After the 2nd pass
After the 3rd pass
After the 4th pass
If we fed edges in order from 1 to last, we could find the shortest lengths after the 1st pass.
|