Determine negative-weight cycle in a graph

Given a directed weighted graph, report a negative-weight cycle in the graph if any. A negative-weight cycle is a cycle in graph whose edges sum to a negative value.


 

For example, consider below graph –

negative-weight cycle

It has one negative-weight cycle 1-2-3-1 with sum -2.

 


 

Approach 1: Using Bellman–Ford algorithm

 
Bellman–Ford algorithm is used to compute the shortest paths from a single source vertex to all of the other vertices in given weighted digraph. It can be modified to report any negative-weight cycle in the graph.

To find if the graph contains negative weight cycle, we run Bellman-Ford once from each vertex. The idea is after running relaxation step in Bellman-Ford V-1 times, a final scan of all the edges is performed and if any distance is updated, then a path of length |V| edges has been found which can only occur if at least one negative cycle exists in the graph.

The time complexity of this approach will be O(V2E). If the graph is dense i.e. E = V2, then the time complexity becomes O(V4).

 
C++ implementation –
 

Download   Run Code

Output:


Negative Weight Cycle Found!!

 

Approach 2: Using Floyd–Warshall Algorithm

 
Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. It can easily be modified to report any negative-weight cycle in the graph.

To detect negative cycles using the Floyd–Warshall algorithm, we need to the check diagonal of the cost matrix for presence of any negative number as it indicates that the graph contains at least one negative cycle. The Floyd–Warshall algorithm iteratively revises path lengths between all pairs of vertices (i, j), including where i = j. Initially, the length of the path (i, i) is zero. A path
[i, k...i] can only improve upon this if it has length less than zero, i.e. denotes a negative cycle. Thus, after the algorithm, (i, i) will be negative if there exists a negative-length path from i back to i. The time complexity of this approach is O(V3) where V is number of vertices in the graph.

 
C++ implementation –

 

Download   Run Code

Output:


Negative Weight Cycle Found!!

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of