Given a directed weighted graph, the task is to find whether the given graph contains any negative-weight cycle or not.
Note: A negative-weight cycle is a cycle in a graph whose edges sum to a negative value.
Example:
Input:
Example 1
Output: No
Input:
Example 2
Output: Yes
Algorithm to Find Negative Cycle in a Directed Weighted Graph Using Bellman-Ford:
- Initialize distance array dist[] for each vertex ‘v‘ as dist[v] = INFINITY.
- Assume any vertex (let’s say ‘0’) as source and assign dist = 0.
- Relax all the edges(u,v,weight) N-1 times as per the below condition:
- dist[v] = minimum(dist[v], distance[u] + weight)
- Now, Relax all the edges one more time i.e. the Nth time and based on the below two cases we can detect the negative cycle:
- Case 1 (Negative cycle exists): For any edge(u, v, weight), if dist[u] + weight < dist[v]
- Case 2 (No Negative cycle) : case 1 fails for all the edges.
Working of Bellman-Ford Algorithm to Detect the Negative cycle in the graph:
Let’s suppose we have a graph which is given below and we want to find whether there exists a negative cycle or not using Bellman-Ford.
Initial Graph
Step-1: Initialize a distance array Dist[] to store the shortest distance for each vertex from the source vertex. Initially distance of source will be 0 and Distance of other vertices will be INFINITY.
Initialize a distance array
Step 2: Start relaxing the edges, during 1st Relaxation:
- Current Distance of B > (Distance of A) + (Weight of A to B) i.e. Infinity > 0 + 5
- Therefore, Dist[B] = 5
1st Relaxation
Step 3: During 2nd Relaxation:
- Current Distance of D > (Distance of B) + (Weight of B to D) i.e. Infinity > 5 + 2
- Dist[D] = 7
- Current Distance of C > (Distance of B) + (Weight of B to C) i.e. Infinity > 5 + 1
- Dist[C] = 6
2nd Relaxation
Step 4: During 3rd Relaxation:
- Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. Infinity > 7 + 2
- Dist[F] = 9
- Current Distance of E > (Distance of C ) + (Weight of C to E) i.e. Infinity > 6 + 1
- Dist[E] = 7
3rd Relaxation
Step 5: During 4th Relaxation:
- Current Distance of D > (Distance of E) + (Weight of E to D) i.e. 7 > 7 + (-1)
- Dist[D] = 6
- Current Distance of E > (Distance of F ) + (Weight of F to E) i.e. 7 > 9 + (-3)
- Dist[E] = 6
4th Relaxation
Step 6: During 5th Relaxation:
- Current Distance of F > (Distance of D) + (Weight of D to F) i.e. 9 > 6 + 2
- Dist[F] = 8
- Current Distance of D > (Distance of E ) + (Weight of E to D) i.e. 6 > 6 + (-1)
- Dist[E] = 5
- Since the graph h 6 vertices, So during the 5th relaxation the shortest distance for all the vertices should have been calculated.
5th Relaxation
Step 7: Now the final relaxation i.e. the 6th relaxation should indicate the presence of negative cycle if there is any changes in the distance array of 5th relaxation.
During the 6th relaxation, following changes can be seen:
- Current Distance of E > (Distance of F) + (Weight of F to E) i.e. 6 > 8 + (-3)
- Dist[E]=5
- Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. 8 > 5 + 2
- Dist[F]=7
Since we observer changes in the Distance array Hence ,we can conclude the presence of a negative cycle in the graph.
6th Relaxation
Result: A negative cycle (D->F->E) exists in the graph.
Below is the implementation to detect Negative cycle in a graph:
C++
// A C++ program for Bellman-Ford's single source// shortest path algorithm.#include <bits/stdc++.h>using namespace std;// A structure to represent a weighted edge in graphstruct Edge { int src, dest, weight;};// A structure to represent a connected, directed and// weighted graphstruct Graph { // V-> Number of vertices, E-> Number of edges int V, E; // Graph is represented as an array of edges. struct Edge* edge;};// Creates a graph with V vertices and E edgesstruct Graph* createGraph(int V, int E){ struct Graph* graph = new Graph; graph->V = V; graph->E = E; graph->edge = new Edge[graph->E]; return graph;}// The main function that finds shortest distances// from src to all other vertices using Bellman-// Ford algorithm. The function also detects// negative weight cyclebool isNegCycleBellmanFord(struct Graph* graph, int src, int dist[]){ int V = graph->V; int E = graph->E; // Step 1: Initialize distances from src // to all other vertices as INFINITE for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. // A simple shortest path from src to any // other vertex can have at-most |V| - 1 // edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->edge[j].src; int v = graph->edge[j].dest; int weight = graph->edge[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. // The above step guarantees shortest distances // if graph doesn't contain negative weight cycle. // If we get a shorter path, then there // is a cycle. for (int i = 0; i < E; i++) { int u = graph->edge[i].src; int v = graph->edge[i].dest; int weight = graph->edge[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) return true; } return false;}// Returns true if given graph has negative weight// cycle.bool isNegCycleDisconnected(struct Graph* graph){ int V = graph->V; // To keep track of visited vertices to avoid // recomputations. bool visited[V]; memset(visited, 0, sizeof(visited)); // This array is filled by Bellman-Ford int dist[V]; // Call Bellman-Ford for all those vertices // that are not visited for (int i = 0; i < V; i++) { if (visited[i] == false) { // If cycle found if (isNegCycleBellmanFord(graph, i, dist)) return true; // Mark all vertices that are visited // in above call. for (int i = 0; i < V; i++) if (dist[i] != INT_MAX) visited[i] = true; } } return false;}// Driver Codeint main(){ // Number of vertices in graph int V = 5; // Number of edges in graph int E = 8; // Let us create the graph given in above example struct Graph* graph = createGraph(V, E); graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = -1; graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].weight = 4; graph->edge[2].src = 1; graph->edge[2].dest = 2; graph->edge[2].weight = 3; graph->edge[3].src = 1; graph->edge[3].dest = 3; graph->edge[3].weight = 2; graph->edge[4].src = 1; graph->edge[4].dest = 4; graph->edge[4].weight = 2; graph->edge[5].src = 3; graph->edge[5].dest = 2; graph->edge[5].weight = 5; graph->edge[6].src = 3; graph->edge[6].dest = 1; graph->edge[6].weight = 1; graph->edge[7].src = 4; graph->edge[7].dest = 3; graph->edge[7].weight = -3; if (isNegCycleDisconnected(graph)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// A Java program for Bellman-Ford's single source// shortest path algorithm.import java.util.*;class GFG { // A structure to represent a weighted // edge in graph static class Edge { int src, dest, weight; } // A structure to represent a connected, // directed and weighted graph static class Graph { // V-> Number of vertices, // E-> Number of edges int V, E; // Graph is represented as // an array of edges. Edge edge[]; } // Creates a graph with V vertices and E edges static Graph createGraph(int V, int E) { Graph graph = new Graph(); graph.V = V; graph.E = E; graph.edge = new Edge[graph.E]; for (int i = 0; i < graph.E; i++) { graph.edge[i] = new Edge(); } return graph; } // The main function that finds shortest distances // from src to all other vertices using Bellman- // Ford algorithm. The function also detects // negative weight cycle static boolean isNegCycleBellmanFord(Graph graph, int src, int dist[]) { int V = graph.V; int E = graph.E; // Step 1: Initialize distances from src // to all other vertices as INFINITE for (int i = 0; i < V; i++) dist[i] = Integer.MAX_VALUE; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. // A simple shortest path from src to any // other vertex can have at-most |V| - 1 // edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. // The above step guarantees shortest distances // if graph doesn't contain negative weight cycle. // If we get a shorter path, then there // is a cycle. for (int i = 0; i < E; i++) { int u = graph.edge[i].src; int v = graph.edge[i].dest; int weight = graph.edge[i].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) return true; } return false; } // Returns true if given graph has negative weight // cycle. static boolean isNegCycleDisconnected(Graph graph) { int V = graph.V; // To keep track of visited vertices // to avoid recomputations. boolean visited[] = new boolean[V]; Arrays.fill(visited, false); // This array is filled by Bellman-Ford int dist[] = new int[V]; // Call Bellman-Ford for all those vertices // that are not visited for (int i = 0; i < V; i++) { if (visited[i] == false) { // If cycle found if (isNegCycleBellmanFord(graph, i, dist)) return true; // Mark all vertices that are visited // in above call. for (int j = 0; j < V; j++) if (dist[j] != Integer.MAX_VALUE) visited[j] = true; } } return false; } // Driver Code public static void main(String[] args) { int V = 5, E = 8; Graph graph = createGraph(V, E); // Add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // Add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // Add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // Add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // Add edge 1-4 (or A-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // Add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // Add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // Add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; if (isNegCycleDisconnected(graph)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by adityapande88 |
Python
# A Python3 program for Bellman-Ford's single source# shortest path algorithm.# The main function that finds shortest distances# from src to all other vertices using Bellman-# Ford algorithm. The function also detects# negative weight cycledef isNegCycleBellmanFord(src, dist): global graph, V, E # Step 1: Initialize distances from src # to all other vertices as INFINITE for i in range(V): dist[i] = 10**18 dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. # A simple shortest path from src to any # other vertex can have at-most |V| - 1 # edges for i in range(1, V): for j in range(E): u = graph[j][0] v = graph[j][1] weight = graph[j][2] if (dist[u] != 10**18 and dist[u] + weight < dist[v]): dist[v] = dist[u] + weight # Step 3: check for negative-weight cycles. # The above step guarantees shortest distances # if graph doesn't contain negative weight cycle. # If we get a shorter path, then there # is a cycle. for i in range(E): u = graph[i][0] v = graph[i][1] weight = graph[i][2] if (dist[u] != 10**18 and dist[u] + weight < dist[v]): return True return False# Returns true if given graph has negative weight# cycle.def isNegCycleDisconnected(): global V, E, graph # To keep track of visited vertices to avoid # recomputations. visited = [0]*V # memset(visited, 0, sizeof(visited)) # This array is filled by Bellman-Ford dist = [0]*V # Call Bellman-Ford for all those vertices # that are not visited for i in range(V): if (visited[i] == 0): # If cycle found if (isNegCycleBellmanFord(i, dist)): return True # Mark all vertices that are visited # in above call. for i in range(V): if (dist[i] != 10**18): visited[i] = True return False# Driver codeif __name__ == '__main__': # /* Let us create the graph given in above example */ V = 5 # Number of vertices in graph E = 8 # Number of edges in graph graph = [[0, 0, 0] for i in range(8)] # add edge 0-1 (or A-B in above figure) graph[0][0] = 0 graph[0][1] = 1 graph[0][2] = -1 # add edge 0-2 (or A-C in above figure) graph[1][0] = 0 graph[1][1] = 2 graph[1][2] = 4 # add edge 1-2 (or B-C in above figure) graph[2][0] = 1 graph[2][1] = 2 graph[2][2] = 3 # add edge 1-3 (or B-D in above figure) graph[3][0] = 1 graph[3][1] = 3 graph[3][2] = 2 # add edge 1-4 (or A-E in above figure) graph[4][0] = 1 graph[4][1] = 4 graph[4][2] = 2 # add edge 3-2 (or D-C in above figure) graph[5][0] = 3 graph[5][1] = 2 graph[5][2] = 5 # add edge 3-1 (or D-B in above figure) graph[6][0] = 3 graph[6][1] = 1 graph[6][2] = 1 # add edge 4-3 (or E-D in above figure) graph[7][0] = 4 graph[7][1] = 3 graph[7][2] = -3 if (isNegCycleDisconnected()): print("Yes") else: print("No")# This code is contributed by mohit kumar 29 |
C#
// A C# program for Bellman-Ford's single source// shortest path algorithm.using System;using System.Collections.Generic;public class GFG { // A structure to represent a weighted // edge in graph public class Edge { public int src, dest, weight; } // A structure to represent a connected, // directed and weighted graph public class Graph { // V-> Number of vertices, // E-> Number of edges public int V, E; // Graph is represented as // an array of edges. public Edge[] edge; } // Creates a graph with V vertices and E edges static Graph createGraph(int V, int E) { Graph graph = new Graph(); graph.V = V; graph.E = E; graph.edge = new Edge[graph.E]; for (int i = 0; i < graph.E; i++) { graph.edge[i] = new Edge(); } return graph; } // The main function that finds shortest distances // from src to all other vertices using Bellman- // Ford algorithm. The function also detects // negative weight cycle static bool isNegCycleBellmanFord(Graph graph, int src, int[] dist) { int V = graph.V; int E = graph.E; // Step 1: Initialize distances from src // to all other vertices as INFINITE for (int i = 0; i < V; i++) dist[i] = int.MaxValue; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. // A simple shortest path from src to any // other vertex can have at-most |V| - 1 // edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. // The above step guarantees shortest distances // if graph doesn't contain negative weight cycle. // If we get a shorter path, then there // is a cycle. for (int i = 0; i < E; i++) { int u = graph.edge[i].src; int v = graph.edge[i].dest; int weight = graph.edge[i].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) return true; } return false; } // Returns true if given graph has negative weight // cycle. static bool isNegCycleDisconnected(Graph graph) { int V = graph.V; // To keep track of visited vertices // to avoid recomputations. bool[] visited = new bool[V]; // This array is filled by Bellman-Ford int[] dist = new int[V]; // Call Bellman-Ford for all those vertices // that are not visited for (int i = 0; i < V; i++) { if (visited[i] == false) { // If cycle found if (isNegCycleBellmanFord(graph, i, dist)) return true; // Mark all vertices that are visited // in above call. for (int j = 0; j < V; j++) if (dist[j] != int.MaxValue) visited[j] = true; } } return false; } // Driver Code public static void Main(String[] args) { int V = 5, E = 8; Graph graph = createGraph(V, E); // Add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // Add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // Add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // Add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // Add edge 1-4 (or A-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // Add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // Add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // Add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; if (isNegCycleDisconnected(graph)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by aashish1995 |
Javascript
<script>// A Javascript program for Bellman-Ford's single source// shortest path algorithm. // A structure to represent a weighted // edge in graph class Edge { constructor() { let src, dest, weight; } } // A structure to represent a connected, // directed and weighted graph class Graph { constructor() { // V-> Number of vertices, // E-> Number of edges let V, E; // Graph is represented as // an array of edges. let edge=[]; } } // Creates a graph with V vertices and E edges function createGraph(V,E) { let graph = new Graph(); graph.V = V; graph.E = E; graph.edge = new Array(graph.E); for(let i = 0; i < graph.E; i++) { graph.edge[i] = new Edge(); } return graph; }// The main function that finds shortest distances// from src to all other vertices using Bellman-// Ford algorithm. The function also detects// negative weight cyclefunction isNegCycleBellmanFord(graph,src,dist){ let V = graph.V; let E = graph.E; // Step 1: Initialize distances from src // to all other vertices as INFINITE for(let i = 0; i < V; i++) dist[i] = Number.MAX_VALUE; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. // A simple shortest path from src to any // other vertex can have at-most |V| - 1 // edges for(let i = 1; i <= V - 1; i++) { for(let j = 0; j < E; j++) { let u = graph.edge[j].src; let v = graph.edge[j].dest; let weight = graph.edge[j].weight; if (dist[u] != Number.MAX_VALUE && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. // The above step guarantees shortest distances // if graph doesn't contain negative weight cycle. // If we get a shorter path, then there // is a cycle. for(let i = 0; i < E; i++) { let u = graph.edge[i].src; let v = graph.edge[i].dest; let weight = graph.edge[i].weight; if (dist[u] != Number.MAX_VALUE && dist[u] + weight < dist[v]) return true; } return false;}// Returns true if given graph has negative weight// cycle.function isNegCycleDisconnected(graph){ let V = graph.V; // To keep track of visited vertices // to avoid recomputations. let visited = new Array(V); for(let i=0;i<V;i++) { visited[i]=false; } // This array is filled by Bellman-Ford let dist = new Array(V); // Call Bellman-Ford for all those vertices // that are not visited for(let i = 0; i < V; i++) { if (visited[i] == false) { // If cycle found if (isNegCycleBellmanFord(graph, i, dist)) return true; // Mark all vertices that are visited // in above call. for(let j = 0; j < V; j++) if (dist[j] != Number.MAX_VALUE) visited[j] = true; } } return false;}// Driver Codelet V = 5, E = 8;let graph = createGraph(V, E);// Add edge 0-1 (or A-B in above figure)graph.edge[0].src = 0;graph.edge[0].dest = 1;graph.edge[0].weight = -1;// Add edge 0-2 (or A-C in above figure)graph.edge[1].src = 0;graph.edge[1].dest = 2;graph.edge[1].weight = 4;// Add edge 1-2 (or B-C in above figure)graph.edge[2].src = 1;graph.edge[2].dest = 2;graph.edge[2].weight = 3;// Add edge 1-3 (or B-D in above figure)graph.edge[3].src = 1;graph.edge[3].dest = 3;graph.edge[3].weight = 2;// Add edge 1-4 (or A-E in above figure)graph.edge[4].src = 1;graph.edge[4].dest = 4;graph.edge[4].weight = 2;// Add edge 3-2 (or D-C in above figure)graph.edge[5].src = 3;graph.edge[5].dest = 2;graph.edge[5].weight = 5;// Add edge 3-1 (or D-B in above figure)graph.edge[6].src = 3;graph.edge[6].dest = 1;graph.edge[6].weight = 1;// Add edge 4-3 (or E-D in above figure)graph.edge[7].src = 4;graph.edge[7].dest = 3;graph.edge[7].weight = -3;if (isNegCycleDisconnected(graph)) document.write("Yes");else document.write("No"); // This code is contributed by patel2127</script> |
Output
No
Time Complexity: O(V*E), , where V and E are the number of vertices in the graph and edges respectively.
Auxiliary Space: O(V), where V is the number of vertices in the graph.
Related articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
