Bellman–Ford and detecting a negative cycle
Problem
Find the shortest distances from a source in a graph whose edges may have negative weights, and report whether the graph contains a negative-weight cycle (in which case shortest paths are undefined).
Example 1
Input: edges = [[0,1,-1], [0,2,4], [1,2,3], [1,3,2], [1,4,2], [3,2,5], [3,1,1], [4,3,-3]], source 0 Output: [0, -1, 2, -2, 1], no negative cycle
Also asked as: Implement Bellman Ford Algorithm · Detect Negative cycle in a graph
Test cases
Case 1
Input: 5, [[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]], 0
Expected: {"dist":[0,-1,2,-2,1]}Case 2
Input: 3, [[0,1,1],[1,2,-1],[2,0,-1]], 0
Expected: {"negativeCycle":true}Case 3
Input: 2, [[0,1,4]], 0
Expected: {"dist":[0,4]}Case 4
Input: 1, [], 0
Expected: {"dist":[0]}View solutionHide solution1 approach
1. Relax all edges V−1 times; a further relaxation means a negative cycle
Time O(V·E)Space O(V)
Handles negative weights. If any edge can still be relaxed after V−1 rounds, a negative cycle is reachable.
function bellmanFord(n, edges, src) { // edges: [u, v, w] const dist = new Array(n).fill(Infinity); dist[src] = 0; for (let i = 0; i < n - 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 { negativeCycle: true }; return { dist };}