#include<iostream>
using namespace std;
#define MAX 9999
typedef struct edge
{
int s;
int d;
int w;
}edge;
void bellman(int nv,edge e[],int sv,int ne)
{
int u,v,weight,i,j=0;
int dis[MAX];
int parent[MAX]; // to keep each nodes parent
//assigning infinity to the weights
for(i=0;i<nv;i++)
{
dis[i]=MAX;
}
// distance of source vertex is o
dis[sv]=0;
parent[sv] = NULL; // source nodes parent is null
//relaxing the edges v-1 time
for(i=0;i<nv-1;i++)
{
for(j=0;j<ne;j++)
{
u=e[j].s;
v=e[j].d;
weight=e[j].w;
if(dis[u]+weight < dis[v] && dis[u]!=MAX)
{
dis[v]=dis[u]+weight;
parent[v] = u;
}
}
}
//negative cycle check
for(j=0;j<ne;j++)
{
u=e[j].s;
v=e[j].d;
weight=e[j].w;
if(dis[u]+weight < dis[v])
{
cout<<"\nThere is no shortest path.\n";
return;
}
}
cout<<"\nVertex"<<" Shortest Cost From Source"<<" Path";
for(i=0;i<nv;i++)
{
cout<<"\n"<<i<<"\t"<<dis[i]<<"\t"<<"\t"<<"\t"<<"\t";
//path
int x = i;
while(1){
cout<<x<<"<-";
x = parent[x];
if(x == NULL) break;
}
}
}
int main()
{
int nv,ne,sv;
edge e[MAX];
cout<<"Enter the number of vertex: ";
cin>>nv;
printf("Enter the source vertex of the graph: ");
cin>>sv;
cout<<"\nEnter no. of edges: ";
cin>>ne;
for(int i=0;i<ne;i++)
{
cout<<"\nFor "<<i+1<<"th Edge =>\n";
cout<<"Enter Source, Destination & Edge Weight :";
cin>>e[i].s>>e[i].d>>e[i].w;
}
bellman(nv,e,sv,ne);
return 0;
}