Detect Negative cycle in a graph
Problem Statement
Given a weighted directed graph, detect whether the graph contains a negative weight cycle. A negative weight cycle is a cycle in the graph where the sum of all edge weights is negative.
Example:
- Input:
V = 4, edges = [(0,1,1), (1,2,-1), (2,3,-1), (3,0,-1)] - Output:
true(cycle 0→1→2→3→0 has total weight 1 + (-1) + (-1) + (-1) = -2)
Noob-Friendly Explanation
Imagine you're a currency trader. Each exchange has a rate (could be positive or negative). A negative cycle is like finding a loop of trades where you end up with more money each time you go around the loop — it seems great but in graph theory it causes problems because shortest paths become undefined (you can always go around the loop once more to get a shorter path).
Bellman-Ford algorithm relaxes edges V-1 times. If after V-1 rounds we can still relax an edge, there must be a negative cycle.
Approach 1: Brute Force (DFS-based)
Intuition
Use DFS to detect cycles. For each cycle found, calculate the total weight. If any cycle has a negative total weight, a negative cycle exists. This approach tries all possible paths.
Algorithm
- For each vertex, start DFS and track the current path and its weight.
- If we revisit a vertex that's in the current path, we've found a cycle.
- Calculate the cycle's total weight. If negative, report it.
import java.util.*;
public class NegCycleDFS {
static boolean found = false;
public static boolean hasNegativeCycle(int V, int[][] edges) {
// Build adjacency list with weights
Map<Integer, List<int[]>> adj = new HashMap<>();
for (int i = 0; i < V; i++) adj.put(i, new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(new int[]{e[1], e[2]});
}
found = false;
int[] pathWeight = new int[V];
boolean[] visited = new boolean[V];
boolean[] inStack = new boolean[V];
for (int i = 0; i < V && !found; i++) {
if (!visited[i]) {
dfs(i, adj, visited, inStack, pathWeight, 0);
}
}
return found;
}
static void dfs(int u, Map<Integer, List<int[]>> adj,
boolean[] visited, boolean[] inStack,
int[] distTo, int currDist) {
if (found) return;
visited[u] = true;
inStack[u] = true;
distTo[u] = currDist;
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (inStack[v]) {
// Found a cycle: weight = currDist + w - distTo[v]
int cycleWeight = currDist + w - distTo[v];
if (cycleWeight < 0) {
found = true;
return;
}
} else if (!visited[v]) {
dfs(v, adj, visited, inStack, distTo, currDist + w);
}
}
inStack[u] = false;
}
public static void main(String[] args) {
int V = 4;
int[][] edges = {
{0, 1, 1}, {1, 2, -1}, {2, 3, -1}, {3, 0, -1}
};
System.out.println("Has negative cycle: " + hasNegativeCycle(V, edges));
}
}Complexity Analysis
- Time Complexity: O(V * E) - in the worst case, DFS explores all edges from all vertices
- Space Complexity: O(V) - for visited, inStack, and recursion stack
Approach 2: Optimal (Bellman-Ford Algorithm)
Intuition
Bellman-Ford algorithm relaxes all edges V-1 times. After V-1 relaxations, shortest distances are finalized (if no negative cycle exists). If we run one more (Vth) relaxation and any distance still decreases, a negative cycle exists.
Algorithm
- Initialize distances:
dist[source] = 0, all others = infinity. - Relax all edges V-1 times.
- Run one more relaxation. If any distance decreases, a negative cycle exists.
import java.util.*;
public class NegCycleBellmanFord {
public static boolean hasNegativeCycle(int V, int[][] edges) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
// Relax all edges V-1 times
for (int i = 0; i < V - 1; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Check for negative cycle: Vth relaxation
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
return true; // Negative cycle detected
}
}
return false;
}
public static void main(String[] args) {
int V = 4;
int[][] edges = {
{0, 1, 1}, {1, 2, -1}, {2, 3, -1}, {3, 0, -1}
};
System.out.println("Has negative cycle: " + hasNegativeCycle(V, edges));
}
}Complexity Analysis
- Time Complexity: O(V * E) - V-1 relaxation rounds, each processing all E edges
- Space Complexity: O(V) - for the distance array