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

Given a weighted directed graph, detect if it contains a negative weight cycle using Bellman-Ford algorithm.

Example: V=4, edges=[[0,1,-1],[1,2,-2],[2,3,-3],[3,0,4]] → false (no negative cycle)

Sample Input

—

Sample Output

—

Constraints

1 <= V <= 100
1 <= E <= V*(V-1)
-10^3 <= weight <= 10^3

Topics

Graph BFS DFS

Bellman-Ford

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

function hasNegativeCycle(V, edges) {
  const dist = Array(V).fill(Infinity);
  dist[0] = 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.