Negative Cycles in Bellman-Ford

Question

In a directed graph with V nodes and E edges, the Bellman-Ford algorithm relaxes every vertex (or rather, the edges going out of every vertex) (V - 1) times. This is because the shortest path from the source to any other node contains at most (V - 1) edges. In the V-th iteration, if an edge can be relaxed, it indicates the presence of a negative cycle.

Now, I need to find the other nodes "ruined" by this negative cycle. That is, some nodes not on the negative cycle now have a distance of negative infinity from the source because of one or more nodes on the path from the source to the node that lie in a negative cycle.

One way to accomplish this is to run Bellman-Ford and take note of the nodes on negative cycles. Then, run DFS/BFS from these nodes to mark other nodes.

However, why can't we run the Bellman-Ford 2 * (V - 1) times to detect such nodes without resorting to DFS/BFS? If my understanding is right, relaxing all vertices 2 * (V - 1) times should allow the negative cycles to "propagate" their values to all other connected nodes.

Additional Details: I encountered this situation when solving this online problem: https://open.kattis.com/problems/shortestpath3

The Java code that I used (along with BFS/DFS that is not shown here) is as follows:

  // Relax all vertices n - 1 times.
  // And relax one more time to find negative cycles
  for (int vv = 1; vv <= n; vv++) {
    // Relax each vertex
    for (int v = 0; v < n; v++) {
      // For each edge
      if (distTo[v] != (int) 1e9) {
        for (int i = 0; i < adjList[v].size(); i++) {
          int dest = adjList[v].get(i).fst;
          int wt = adjList[v].get(i).snd;

          if (distTo[v] + wt < distTo[dest]) {
            distTo[dest] = distTo[v] + wt;

            if (vv == n) {
              isInfinite[v] = true;
              isInfinite[dest] = true;
            }
          }
        }
      }
    }
  }

Owen Leong Owen Leong · Accepted Answer · 2020-04-08T10:14:51

Consider a graph with N=4, M=5:

A -> B weight 1000
A -> C weight 1000
C -> D weight -1
D -> C weight -1
D -> B weight 1000

Let A be our source and B be the destination.

Now obviously there is a negative cycle (C <-> D). But whether we run the algorithm N times or 2N times or even 3N times, the shortest path from A to B is still 1000. Since the negative cycle only reduces the distance by a small amount every time it is used, it does not propogate to the other nodes as we expect it to.

A solution would be to mark the distance as negative infinity once a cycle affecting a node is identified. That way the negative cycle "takes precendence" over other shortest paths through other nodes.

Yours sincerely,
A fellow coder who has spent lots of time on this problem.

Negative Cycles in Bellman-Ford

2 Answers