blob: 94fa0349b48afe400606362cbb889ece499e97d8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//n = number of vertices, edges is vector of edges
dist.assign(n, INF); dist[0] = 0;
parent.assign(n, -1);
for (i = 0; i < n - 1; i++) {
for (j = 0; j < (int)edges.size(); j++) {
if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) {
dist[edges[j].to] = dist[edges[j].from] + edges[j].cost;
parent[edges[j].to] = edges[j].from;
}
}
}
//now dist and parent are correct shortest paths
//next lines check for negative cycles
for (j = 0; j < (int)edges.size(); j++) {
if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) {
//NEGATIVE CYCLE found
}
}
|
