# Detect a Negative Cycle in a Graph using Shortest Path Faster Algorithm

Riya
Last Updated: May 13, 2022

## Introduction-

This blog will discuss how to detect a negative cycle using shortest path faster algorithm in a given graph. We will be given a weighted and directed graph, and we have to find if it contains a negative cycle or not using the shortest path faster algorithm. Before proceeding, let's recall what a negative cycle in a graph means.

"A cycle in a graph is known as a negative cycle if the sum of all the edge weights in that cycle is negative".

Now, let's understand the problem with an example:

In this problem, to detect a negative cycle using shortest path faster algorithm, we will be given a graph with 'N' nodes with values [0, N-1], a source vertex 'S', and a 2-D array denoting there is a directed edge from 'edge[i][0]' to 'edge[i][1]' with weight' edge[0][2]'. And, our task is to detect a negative cycle using shortest path faster algorithm in the given graph.

Example:

We have the graph given below and source vertex ‘s’ = 1

We can see here that in cycle 1->2->3->1, the sum of all the edge weights is equal to '-4' (-3-2+1). So, we have detected a negative cycle in the given graph starting from the given source.

So, now we have understood what a negative cycle is and what we have to detect in the given graph. In this blog, we will see an approach to detect the negative cycle using a particular algorithm, i.e., "shortest path faster algorithm".

## Solution Approach using shortest path faster algorithm

This approach is a modification of the Bellman-Ford Algorithm. We will similarly relax the vertices, but there is a modification that in "Bellman-Ford algorithm", we tried relaxing the vertices "N-1" times where 'N' is the number of vertices in the graph. In contrast, in this approach, we will store the vertex that has been relaxed, and in the next step, we will relax only those vertices adjacent to the stored vertex.

In this approach to detect a negative cycle, we will be trying to relax each vertex, and if a vertex will be relaxed, we will insert that vertex into a queue so that now we can relax all the vertices which are adjacent to that vertex. In this way, we will keep relaxing the vertices until the queue becomes empty.

Here "relaxing a vertex" means to check for an edge 'u' to 'v', if the distance of v is greater than the sum of the weight of u-v edge and distance of 'u', then update the distance of 'v' as the sum of the distance of 'u' and weight of the edge 'u-v'.

## Algorithm -

Step 1. Create a function "detectCycleUsingSpfa()" to detect a negative cycle in a graph using Shortest Path Faster Algorithm, which takes the following inputs:

1. N - number of nodes in the graph
2. M - number of edges in the graph
3. S - source vertex
4. graph - Adjacency list representation of the graph

Step 2. Initialize the "distance" vector with large values to store the distance from the source vertex to all other vertices. Create a 'queue' to store the nodes that are getting relaxed in the current step and a vector of boolean values "isPresent" to keep track of the nodes present in the queue. And also, create a "count" vector to keep a count of the number of times each vertex has been relaxed.

Step 3.  Mark the distance of source = 0 and insert it into the queue. Now while the queue is not empty, take out the front node from the queue and try to relax the vertices which are adjacent to that node. If a node is relaxed in the current step, increase its relaxation count and insert it into the queue if it is not already present in it.

Step 4. When the count of relaxation is increased for a node, check if the count is greater than N-1, then it means that the graph has a negative cycle, so return true.

Step 5. After the completion of the "while loop", it means that we have not found the negative cycle in the graph, so return false.

## Algorithm Complexity:

Time Complexity: O(N * M)

In function "detectCycleUsingSpfa()" to detect a negative cycle in a graph using Shortest Path Faster Algorithm, we are relaxing each edge for each vertex in the queue. In the worst case, the time complexity will be (N * M) where 'N' and 'M' are the number of nodes and edges, respectively.

Space Complexity: O(N + M)

In function "detectCycleUsingSpfa()" to detect a negative cycle in a graph using Shortest Path Faster Algorithm, we have created an adjacency list representation of the graph, a queue, a "distance" vector, and a boolean vector for keeping track of nodes that are there in the queue. So, the overall space complexity will be O(N + M), where 'N' and 'M' are the number of nodes and edges, respectively.

1. Why do we use the queue data structure in the algorithm to detect a negative cycle using shortest path faster algorithm?

We use the queue data structure to store the vertices which are relaxed in the current step so that in the next step, we will try to relax those vertices only which are adjacent to the vertices which have been relaxed. In this way, we can get better average time complexity as we are not trying to relax all the vertices unnecessarily.

2. Is the "shortest path faster algorithm" has better worst-case time complexity as compared to the "Bellman-Ford algorithm"?

The worst-case time complexity for "shortest path faster algorithm" and "Bellman-Ford algorithm" is the same, but the average case time complexity of "shortest path faster algorithm" is better as compared to "Bellman-Ford Algorithm".

## Key takeaways-

In this article, we discussed how to detect a negative cycle using shortest path faster algorithm in a given graph, its C++ implementation, and its time and space complexity. If you want to solve problems related to the graph data structure for practice, then you can visit codestudio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.