Detect a negative cycle in a Graph | (Bellman Ford) Medium 0 attempts
GeeksforGeeks ↗

Detect a negative cycle in a Graph | (Bellman Ford)

Medium GraphBFSDFS GeeksforGeeks

You're given a weighted, directed graph with V vertices and a list of edges. Determine whether it contains a negative-weight cycle — a cycle whose edge weights sum to less than zero — using the Bellman-Ford shortest-path algorithm.

Input Format
Implement hasNegativeCycle(V, edges). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
V = 4
edges = [[0,1,-1],[1,2,-2],[2,3,-3],[3,0,4]]
Output
true

Example 2

Input
V = 4
edges = [[2,3,-1],[3,2,-1]]
Output
true

Example 3

Input
V = 3
edges = [[0,1,-1],[1,2,2]]
Output
false
Constraints
  • 1 <= V <= 100
  • 1 <= E <= V*(V-1)
  • -10^3 <= weight <= 10^3
Test Cases (3)
Case 1
Args: [4,[[0,1,-1],[1,2,-2],[2,3,-3],[3,0,4]]] Expected: true
Case 2
Args: [4,[[2,3,-1],[3,2,-1]]] Expected: true
Case 3
Args: [3,[[0,1,-1],[1,2,2]]] Expected: false
Topics
GraphBFSDFS

Bellman-Ford

Run V-1 relaxations, then check if any edge can still be relaxed.

javascript
function hasNegativeCycle(V, edges) {
  // A virtual source reaches every component with a zero-weight edge.
  const dist = Array(V).fill(0);
  for (let i = 0; i < V - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
  }
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) return true;
  }
  return false;
}

Time: O(V × E) | Space: O(V)

Saved in this browser only. Private to you.

JavaScript