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

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.
 

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; } You can also try this code with Online C++ Compiler Run Code

Output: Yes, the given graph has a negative cycle starting with the given source! You can also try this code with Online C++ Compiler Run Code

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-

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 Coding Ninjas Studio.

Check out this problem - Root To Leaf Path

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.