-
Notifications
You must be signed in to change notification settings - Fork 1
/
Single_Source_Shortest_Path_(Bellman_Ford).cpp
98 lines (98 loc) · 1.92 KB
/
Single_Source_Shortest_Path_(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
vector<long long> bellman_ford(vector<vector<pair<int, int>>> &E, int s){
int V = E.size();
vector<long long> d(V, INF);
d[s] = 0;
while (1){
bool update = false;
for (int i = 0; i < V; i++){
for (int j = 0; j < E[i].size(); j++){
int c = E[i][j].first;
int v = E[i][j].second;
if (d[v] > d[i] + c && d[i] != INF){
d[v] = d[i] + c;
update = true;
}
}
}
if (!update){
break;
}
}
return d;
}
bool detect_negative_cycles(vector<vector<pair<int, int>>> &E, int s){
int V = E.size();
vector<long long> d(V, INF);
d[s] = 0;
for (int i = 0; i < V; i++){
bool update = false;
for (int j = 0; j < V; j++){
for (int k = 0; k < E[j].size(); k++){
int c = E[j][k].first;
int v = E[j][k].second;
if (d[v] > d[j] + c && d[j] != INF){
d[v] = d[j] + c;
update = true;
if (i == V - 1){
return true;
}
}
}
}
if (!update){
break;
}
}
return false;
}
bool detect_negative_cycles_2(vector<vector<pair<int, int>>> &E){
int V = E.size();
vector<long long> d(V, 0);
for (int i = 0; i < V; i++){
bool update = false;
for (int j = 0; j < V; j++){
for (int k = 0; k < E[j].size(); k++){
int c = E[j][k].first;
int v = E[j][k].second;
if (d[v] > d[j] + c && d[j] != INF){
d[v] = d[j] + c;
update = true;
if (i == V - 1){
return true;
}
}
}
}
if (!update){
break;
}
}
return false;
}
vector<bool> find_negative_cycles(vector<vector<pair<int, int>>> &E){
int V = E.size();
vector<long long> d(V, 0);
for (int i = 0; i < V; i++){
bool update = false;
for (int j = 0; j < V; j++){
for (int k = 0; k < E[j].size(); k++){
int c = E[j][k].first;
int v = E[j][k].second;
if (d[v] > d[j] + c){
d[v] = d[j] + c;
update = true;
}
}
}
if (!update){
break;
}
}
vector<bool> res(V, false);
for (int i = 0; i < V; i++){
if (d[i] < 0){
res[i] = true;
}
}
return res;
}