BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM

BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM

/*************************************************************************

-> This C++ program is to implement Bellmen Ford algorithm.

-> Bellmen Ford algorithm solves the single source shortest paths
problem in the general case in which edge weights may be negative.

-> This algorithm returns true if the graph contains no
negative-weight cycles that are reachable from the source
else returns the shortest paths from the source.

-> This program works in Microsoft VC++ environment in windows xp

-> Data structures used:
Graph :: Adjacency matrix

-> Header files used :
1)iostream.h
2)stdlib.h

/*************************************************************************/

#include
#include

#define MAX 20
#define INFINITY 9999

class bell_ford
{
private:
int n;
int graph[MAX][MAX];
int start;
int distance[MAX];
int predecessor[MAX];
public:
void read_graph();
void initialize();
void update();
void check();
void algorithm();
};

void bell_ford::read_graph()
{
cout<<”Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<”Enter the adjacency matrix for the graph ::\n”;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>graph[i][j];
cout<<”Enter the start vertex ::”;
cin>>start;
}

void bell_ford::initialize()
{
for(int i=1;i<=n;i++)
{
distance[i]=INFINITY;
predecessor[i]=0;
}
distance[start]=0;
}

void bell_ford::update()
{
for(int i=1;i<=n-1;i++)
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(graph[u][v]!=0)
{
if(distance[v]>distance[u]+graph[u][v])
{
distance[v]=distance[u]+graph[u][v];
predecessor[v]=u;
}
}
}
}
}
}

void bell_ford::check()
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(graph[u][v]!=0)
{
if(distance[v]>distance[u]+graph[u][v])
{
cout<<”does not exist’s “;
return;
}
}
}
}

cout<<”\n\nThere is no negative weight cycle and\n”;
cout<<”****** The final paths and the distacnes are ******\n\n”;
for(int i=1;i<=n;i++)
{
cout<<”path for node “< int arr[MAX],k=1;
int j=i;
while(predecessor[j]!=0)
{
arr[k]=predecessor[j];
k++;
j=predecessor[j];
}
for(–k;k>0;k–)
cout<”;
cout< cout<<”distance is “< }
}

void bell_ford::algorithm()
{
read_graph();
initialize();
update();
check();
}

void main()
{
bell_ford obj;
obj.algorithm();
}