Skip to content

Added more information in finding negative cycle using Bellman-Ford #1299

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Jul 11, 2024
Merged

Added more information in finding negative cycle using Bellman-Ford #1299

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
3b43753
Added more information in finding negative cycle using Bellman-Ford
svaderia Jun 27, 2024
e6903c9
fix spacing
adamant-pwn Jul 11, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
13 changes: 7 additions & 6 deletions src/graph/finding-negative-cycle-in-graph.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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
Expand All @@ -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;
}
}
}
Expand Down
Loading