Merge pull request #1299 from svaderia/patch-2

adamant-pwn · web-flow · commit 8d9bddc605f2 · 2024-07-11T16:22:40.000+02:00
Added more information in finding negative cycle using Bellman-Ford
diff --git a/src/graph/finding-negative-cycle-in-graph.md b/src/graph/finding-negative-cycle-in-graph.md
@@ -19,6 +19,9 @@ Bellman-Ford algorithm allows you to check whether there exists a cycle of negat
 The details of the algorithm are described in the article on the [Bellman-Ford](bellman_ford.md) algorithm.
 Here we'll describe only its application to this problem.
 
+The standard implementation of Bellman-Ford looks for a negative cycle reachable from some starting vertex $v$ ; however, the algorithm can be modified to just looking for any negative cycle in the graph. 
+For this we need to put all the distance  $d[i]$  to zero and not infinity — as if we are looking for the shortest path from all vertices simultaneously; the validity of the detection of a negative cycle is not affected.
+
 Do $N$ iterations of Bellman-Ford algorithm. If there were no changes on the last iteration, there is no cycle of negative weight in the graph. Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found. This cycle will be the desired cycle of negative weight.
 
 ### Implementation
@@ -40,12 +43,10 @@ void solve()
     for (int i = 0; i < n; ++i) {
         x = -1;
         for (Edge e : edges) {
-            if(d[e.a] < INF){
-                if (d[e.a] + e.cost < d[e.b]) {
-                    d[e.b] = max(-INF, d[e.a] + e.cost);
-                    p[e.b] = e.a;
-                    x = e.b;
-                }
+            if (d[e.a] + e.cost < d[e.b]) {
+                d[e.b] = max(-INF, d[e.a] + e.cost);
+                p[e.b] = e.a;
+                x = e.b;
             }
         }
     }
