Description: Implement the Bellman Ford Algorithm

Algorithm:

Relax step

Relax( u,v,w )

If v.d> u.d +w(u,v)

v.d = u.d + w(u,v)

v.p = u

Step 1: Initialize distances from source to all other vertices as INFINITE but source to source as 0

Step 2: Relax all edges |V| - 1 times. A simple shortest path from source to any other vertex can have at-most |V| - 1 edges

Step 3: Check for negative-weight cycles.  The above step guaranteesshortest distances if graph doesn't contain negative weight cycle.If we get a shorter path, then there is a cycle.

C Implementation:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/* a structure to represent a weighted edge in graph */
struct Edge
{
int src, dest, weight;
};

/* a structure to represent a connected, directed and weighted graph */
struct Gr
{
/* V-> Number of vertices, E-> Number of edges */
int V, E;
/* graph is represented as an array of edges. */
struct Edge* edge;
};

/* The following function implements Bellman Ford*/
void BFord(struct Gr* graph, intsrc)
{
int V = graph->V;
int E = graph->E;
int d[V];
/*Initialize distances from src to all other vertices as INFINITE */
for(inti = 0; i < V; i++)
d[i]   = INT_MAX;
d[src] = 0;

/*Step 2: Relax all edges |V| - 1 times */
for(int i = 1; i <= V-1; i++)
{
for(int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if(d[u] + weight < d[v])
d[v] = d[u] + weight;
}
}

/* check for negative-weight cycles */
for(inti = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if(d[u] + weight < d[v])
printf("Negative weight cycle fund");
}
return;
}
Go to top