# 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 –

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).

This is demonstrated below in C++:

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.

This is demonstrated below in C++:

Output:

Negative Weight Cycle Found!!

(2 votes, average: 5.00 out of 5)