Bellman-Ford Algorithm
Bellman Ford Algorithm is a Single-Source Shortest Path Algorithm. It means that it is used to find shortest path from source vertex to all other vertices of a directed/undirected weighted graph. It is used over Dijkstra’s Algorithm when we need to deal with negative weights as Dijkstra’s algorithm fails with negative weights but Bellman Ford algorithm works with negative also.
The algorithm is given below. Here V is the number of vertices of the graph, E stores all edges of the graph and S is the source vertex/node.
u is start vertex of the edge (u,v)
v is end vertex of the edge (u,v)
w is the weight/cost of the edge (u,v)
ALGORITHM:
Initialize-Single Source(G, S)
for i := 1 to |V| — 1 do{ // we relax each edge n-1 times
for each edge (u, v) € E do{
Relax(u, v, w) } }
for each edge (u, v) € E do{
if d[v] = d[u] + w(u, v){ // this is the nth cycle
Then return False } } // this means there is negative cycle
return True
In the algorithm, we first initialize the distances of source vertex as 0 and all other vertices as infinity. Then we relax each edge (n-1) times. Relax means that if we find a new path which is shorter than the previous one then we update the distance of that vertex from the source vertex.
Relax:
if ( d[v] > d[u] + w(u, v) )
{
d[v] = d[u] + w(u, v); // here d[ ] stores distances from source to other vertices
p[v] = u; // update the predecessor node
}
In the case of Bellman Ford, it fails when there is a negative weight cycle in the graph. A negative weight cycle is a cycle with weights that sum to a negative number. It is a problem because if there is a negative weight cycle, we can go on relaxing the nodes infinitely. Hence if we are able to relax an edge after (n-1) times it implies the presence of a negative weight cycle. We know that for a n-vertices graph the shortest path can never contain more than (n-1) egdes, so we run the algorithm (n-1) times and if for the nth time if any distance is reduced then we know there exists a negative weight cycle.
Time Complexity:
· Best: O(E)
· Average: O(VE)
· Worst: O(VE)
Graph:
Let’s take this graph as an example and initialize the distances of source vertex as 0 and all other vertices as infinity.
CODE:
#include <stdio.h>
#include <stdlib.h>
#include<iostream.h>
using namespace std;
#define INFINITY 99999 // very large number for practical use
struct Edge {
int u;
int v;
int w;
};
struct Graph {
int V;
int E;
struct Edge *edge;
};
void display(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
cout<<arr[i]<<” “;
}
cout<<”\n”;
}
void bellmanford(struct Graph *g, int source)
{
int i, j, u, v, w;
int vertex = g->V;
int edges = g->E;
int d[vertex];
int p[vertex];
for (i = 0; i < vertex; i++)
{
d[i] = INFINITY;
p[i] = 0;
}
d[source] = 0;
for (i = 1; i <= vertex — 1; i++)
{
for (j = 0; j < edges; j++)
{
u = g->edge[j].u;
v = g->edge[j].v;
w = g->edge[j].w;
if (d[u] != INFINITY && d[v] > d[u] + w)
{
d[v] = d[u] + w;
p[v] = u;
}
}
}
for (i = 0; i < edges; i++)
{
u = g->edge[i].u;
v = g->edge[i].v;
w = g->edge[i].w;
if (d[u] != INFINITY && d[v] > d[u] + w)
{
cout<<”Negative weight cycle exists!\n”;
return;
}
}
cout<<”Distance array: “;
display(d, vertex);
cout<<”Predecessor array: “;
display(p, vertex);
}
int main()
{
struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));
g->V = 5;
g->E = 8;
g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));
//edge 0 → 1
g->edge[0].u = 0;
g->edge[0].v = 1;
g->edge[0].w = -1;
//edge 0 → 2
g->edge[1].u = 0;
g->edge[1].v = 2;
g->edge[1].w = 4;
//edge 1 → 2
g->edge[2].u = 1;
g->edge[2].v = 2;
g->edge[2].w = 3;
//edge 1 → 3
g->edge[3].u = 1;
g->edge[3].v = 3;
g->edge[3].w = 2;
//edge 3 → 1
g->edge[4].u = 3;
g->edge[4].v = 1;
g->edge[4].w = 1;
//edge 3 → 2
g->edge[5].u = 3;
g->edge[5].v = 2;
g->edge[5].w = 5;
//edge 4 → 3
g->edge[6].u = 4;
g->edge[6].v = 3;
g->edge[6].w = -3;
//edge 1 → 4
g->edge[7].u = 1;
g->edge[7].v = 4;
g->edge[7].w = 2;
bellmanford(g, 0); //0 is the source vertex
return 0;
}
OUTPUT:
