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

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:

N - number of nodes in the graph
M - number of edges in the graph
S - source vertex
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.

C++ code:

// C++ program to detect negative cycle using shortest path faster algorithm
#include <bits/stdc++.h>
using namespace std;


// Function to detect negative cycle using shortest path faster algorithm
bool detectCycleUsingSpfa(int N, int M, int S, vector<vector<pair<int, int>> > graph)
{

// Creating a vector to store distance from source to all other vertices, and initializing with large values
vector<int> distance(N, INT_MAX);

// Creating a queue to keep track of the vertices which are relaxed
queue<int> q;


// Creating a boolean vector to keep track of the vertices present in the queue
vector<bool> isPresent(N, false);


// Creating vector to store the count of relaxation for each vertex
vector<int> count(N, 0);


// Distance of source from source will be 0
distance[S] = 0;


// Pushing the source vertex in the queue
q.push(S);


// Marking that the source vertex is present in the queue
isPresent[S] = true;


while (!q.empty()) 
{


// Take out the front vertex of Queue
int u = q.front();
q.pop();


             // Mark that this vertex is not present in the queue
isPresent[u] = false;


// Relaxing the vertices which are adjacent to u
for (int i=0; i<graph[u].size(); i++) 
{
int v = graph[u][i].first;
int weight = graph[u][i].second;
if (distance[v] > distance[u] + weight) 
{
distance[v] = distance[u] + weight;


// If vertex v is not present in the queue
if (!isPresent[v]) 
{
q.push(v);
isPresent[v] = true;

// Increase the relaxation count for the vertex v
count[v]++;


// Check if the relaxation count for this vertex is greater than N-1, then return true
if (count[v] >= N)
return true;
}
}
}
}


// Now, return false as we have relaxed each vertex and the relaxation count for each vertex is less than N
return false;
}


// Driver Code
int main()
{
// Variable to store given number of vertices
int N = 4;

// Variable to store given number of Edges
int M = 4;


// Variable to store given source vertex
int S = 1;


// A 2-D array to store the given edges with their respective weights
int edges[][3] = { { 0, 1, 2 },
{ 1, 2, -3 },
{ 2, 3, -2 },
{ 3, 1, 1 } };


    // Create adjacency list representation of the graph using the given edges information
    vector<vector<pair<int, int>> > graph(N);
    for (int i = 0; i < M; i++) 
    {
     int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];


        // There will be an edge from u to v with weight w
graph[u].push_back({ v, w });
}
    
// Call the function to detect negative cycle using shortest path faster algorithm
if (detectCycleUsingSpfa(N, M, S, graph)) {
cout << "Yes, the given graph has a negative cycle starting with the given source!" << endl;
}
else {
cout << "No, the given graph doesn't have a negative cycle starting with the given source!" << endl;
}


return 0;
}

Output:
Yes, the given graph has a negative cycle starting with the given source!

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.

Frequently asked questions-

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.