algorithm Bellman–Ford Algorithm Detecting Negative Cycle in a Graph


Example

To understand this example, it is recommended to have a brief idea about Bellman-Ford algorithm which can be found here

Using Bellman-Ford algorithm, we can detect if there is a negative cycle in our graph. We know that, to find out the shortest path, we need to relax all the edges of the graph (V-1) times, where V is the number of vertices in a graph. We have already seen that in this example, after (V-1) iterations, we can't update d[], no matter how many iterations we do. Or can we?

If there is a negative cycle in a graph, even after (V-1) iterations, we can update d[]. This happens because for every iteration, traversing through the negative cycle always decreases the cost of the shortest path. This is why Bellman-Ford algorithm limits the number of iterations to (V-1). If we used Dijkstra's Algorithm here, we'd be stuck in an endless loop. However, let's concentrate on finding negative cycle.

Let's assume, we have a graph:

Example Graph

Let's pick vertex 1 as the source. After applying Bellman-Ford's single source shortest path algorithm to the graph, we'll find out the distances from the source to all the other vertices.

After Applying Bellman Ford

This is how the graph looks like after (V-1) = 3 iterations. It should be the result since there are 4 edges, we need at most 3 iterations to find out the shortest path. So either this is the answer, or there is a negative weight cycle in the graph. To find that, after (V-1) iterations, we do one more final iteration and if the distance continues to decrease, it means that there is definitely a negative weight cycle in the graph.

For this example: if we check 2-3, d[2] + cost[2][3] will give us 1 which is less than d[3]. So we can conclude that there is a negative cycle in our graph.

So how do we find out the negative cycle? We do a bit modification to Bellman-Ford procedure:

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

This is how we find out if there is a negative cycle in a graph. We can also modify Bellman-Ford Algorithm to keep track of negative cycles.