Introduction

Bellman-Ford algorithm is a procedure used to find all shortest path in a graph from one source to all other nodes. The algorithm requires that the graph does not contain any cycles of negative length, but if it does, the algorithm is able to detect it.

The algorithm was introduced by American mathematicians Richard Bellman and Lester Ford.

Description

The Bellman-Ford Algorithm computes the cost of the shortest paths from a starting node to all other nodes in the graph. Thus, it can also construct the paths afterwards.

The algorithm proceeds in an interactive manner, by beginning with a bad estimate of the cost and then improving it until the correct value is found.

The first estimate is:

• The starting node has cost 0, as his distance to itself is obviously 0.

• All other node have cost infinity, which is the worst estimate possible.

Algorithm

d(v[1]) ← 0

FOR j = 2,..,n DO

d(v[j]) ← ∞

FOR i = 1,..,(|V|-1) DO

FOR ALL (u,v) in E DO

d(v) ← min(d(v), d(u)+l(u,v))

FOR ALL (u,v) in E DO

IF d(v) > d(u) + l(u,v) DO

Message: “Negative Circle”

END

C++ (Function)

void BellmanFord(int src)

{

int i, j;

for (i = 0; i < NODES; ++i) d[i] = INFINITY; d[src] = 0; for (i = 0; i < NODES - 1; ++i) { for (j = 0; j < EDGES; ++j) { if (d[edges[j].u] + edges[j].w < d[edges[j].v]) { d[edges[j].v] = d[edges[j].u] + edges[j].w; } } } for (i = 0; i < NODES - 1; ++i) { for (j = 0; j < EDGES; ++j) { if (d[edges[j].u] + edges[j].w < d[edges[j].v]) { printf("Graph contains a negative-weight cycle\n"); exit(1); } } } }

You’re on top of the game. Thanks for shrgina.