-
Notifications
You must be signed in to change notification settings - Fork 490
/
Bellman_Ford.cpp
104 lines (63 loc) Β· 1.88 KB
/
Bellman_Ford.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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**
* Descrption: BellmanFord (Finds the shortest path from source s to all vertices v. Detects a negative weight cycle if present.)
* Usage: See below O(V.E) = O(n^2)
*/
#include <iostream>
#include <vector>
#define INT_MAX 10000
using namespace std;
int V,E;
struct edge{
int src,dst,wt;
};
void bellmanFord(vector<edge>& Edges){
int parent[V]; //To store parent node
//int cost_parent[V]; //Cost of node to parent
vector<int> distance(V,INT_MAX);
parent[0]=-1;
distance[0]=0;
bool update;
for(int i=0;i<V-1;i++){
update=false;
for(int j=0;j<E;j++){
int U=Edges[j].src;
int V=Edges[j].dst;
int wt=Edges[j].wt;
if(distance[U]!=INT_MAX && distance[U]+wt<distance[V]){
distance[V]=distance[U]+wt;
parent[V]=U;
//cost_parent[V]=distance[V];
update=true;
}
}
if(update==false)
break;
}
//Now let's check it has negative edge cycle or not by relaxing one more time
for(int j=0;j<E && update==true;j++){
int U=Edges[j].src;
int V=Edges[j].dst;
int wt=Edges[j].wt;
if(distance[U]!=INT_MAX && distance[U]+wt<distance[V]){
cout<<"Graph has negative Edge Cycle :( "<<endl;
return;
}
}
//Print Shortest path
for(int i=1;i<V;i++){
cout<<"U->V: 0->"<<i<<" Cost to reach "<<i<<" from source 0 = "<<distance[i]<<endl;
}
}
int main(){
cin>>V>>E; //no of vertices and edges
vector<edge> Edges(E);
int src,dst,wt;
for(int i=0;i<E;i++){
cin>>src>>dst>>wt;
Edges[i].src=src;
Edges[i].dst=dst;
Edges[i].wt=wt;
}
bellmanFord(Edges);
return 0;
}