Commita65db14

authored

Update finding-negative-cycle-in-graph.md

Resolves 1419.

1 parent46caa5b commita65db14Copy full SHA for a65db14

File tree

-12

lines changed

-12

lines changed

Lines changed: 9 additions & 12 deletions

Original file line number	Diff line number	Diff line change
`@@ -30,50 +30,47 @@ Do $N$ iterations of Bellman-Ford algorithm. If there were no changes on the las`
`30`	`30`	`structEdge {`
`31`	`31`	`int a, b, cost;`
`32`	`32`	`};`
`33`		`-`
`34`		`-int n, m;`
	`33`	`+`
	`34`	`+int n;`
`35`	`35`	`vector<Edge> edges;`
`36`	`36`	`const int INF = 1000000000;`
`37`		`-`
	`37`	`+`
`38`	`38`	`void solve() {`
`39`		`- vector<int> d(n,INF);`
	`39`	`+ vector<int> d(n,0);`
`40`	`40`	`vector<int> p(n, -1);`
`41`	`41`	`int x;`
`42`		`-`
`43`		`- d[0] = 0;`
`44`		`-`
	`42`	`+`
`45`	`43`	`for (int i = 0; i < n; ++i) {`
`46`	`44`	`x = -1;`
`47`	`45`	`for (Edge e : edges) {`
`48`		`- if (d[e.a]< INF && d[e.a]+ e.cost < d[e.b]) {`
	`46`	`+ if (d[e.a] + e.cost < d[e.b]) {`
`49`	`47`	`d[e.b] = max(-INF, d[e.a] + e.cost);`
`50`	`48`	`p[e.b] = e.a;`
`51`	`49`	`x = e.b;`
`52`	`50`	`}`
`53`	`51`	`}`
`54`	`52`	`}`
`55`		`-`
	`53`	`+`
`56`	`54`	`if (x == -1) {`
`57`	`55`	`cout << "No negative cycle found.";`
`58`	`56`	`} else {`
`59`	`57`	`for (int i = 0; i < n; ++i)`
`60`	`58`	`x = p[x];`
`61`		`-`
	`59`	`+`
`62`	`60`	`vector<int> cycle;`
`63`	`61`	`for (int v = x;; v = p[v]) {`
`64`	`62`	`cycle.push_back(v);`
`65`	`63`	`if (v == x && cycle.size() > 1)`
`66`	`64`	`break;`
`67`	`65`	`}`
`68`	`66`	`reverse(cycle.begin(), cycle.end());`
`69`		`-`
	`67`	`+`
`70`	`68`	`cout << "Negative cycle: ";`
`71`	`69`	`for (int v : cycle)`
`72`	`70`	`cout << v << ' ';`
`73`	`71`	`cout << endl;`
`74`	`72`	`}`
`75`	`73`	`}`
`76`		`-`
`77`	`74`	```
`78`	`75`
`79`	`76`	`##Using Floyd-Warshall algorithm`

Comments

(0)