-
Notifications
You must be signed in to change notification settings - Fork 2
/
BellmanFord.cpp
75 lines (72 loc) · 1.58 KB
/
BellmanFord.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
void bellmanFord()
{
int v,n_edge;
cout<<"enter number of vertices and number of edges "<<endl;
cin>>v>>n_edge;
vector<vector<int>>edges;
for(int i=0;i<n_edge;i++)
{
int u,v,wt;
cout<<"enter start end weight "<<endl;
cin>>u>>v>>wt;
edges.push_back({u,v,wt});
}
vector<int> distance(v,1e7);
vector<int>parent(v,-1);
for(int i=0;i<v;i++)
{
parent[i]=i;
}
int S;
cout<<"enter starting node"<<endl;
cin>>S;
parent[S]=-1;
distance[S]=0;
for(int i=1;i<v;i++)
{
for(auto x:edges)
{
int u=x[0];
int v=x[1];
int wt=x[2];
if(distance[u]+wt<distance[v])
{
parent[v]=u;
distance[v]=distance[u]+wt;
}
}
}
for(auto x:edges)
{
int u=x[0];
int v=x[1];
int wt=x[2];
if(distance[u]+wt<distance[v])
{
cout<<"negative cycle exist !"<<endl;
return ;
}
}
for(int i=0;i<v;i++)
{
if(i!=S)
{
cout<<"distance of "<<i<<"th node from start is :"<<distance[i]<<endl;
cout<<"path follows "<<i;
int j=parent[i];
do
{
cout<<"<-"<<j;
j=parent[j];
}while(j!=-1);
cout<<endl;
}
}
}
int main()
{
bellmanFord();
return 0;
}