Bellman–Ford and detecting a negative cycle

Medium

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]}

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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 };
}