Shortest distances with negative edges
A directed graph has n nodes numbered 0 to n − 1. Each triple
[u, v, w] in edges is an edge from u to v of weight
w, which may be negative.
- If a cycle of negative total weight can be reached from
src, return an empty list. - Otherwise return a list whose entry
vis the smallest total weight of a path fromsrctov, using1000000000(10⁹) for nodes that cannot be reached.
Examples
| Input | Output | Why |
|---|---|---|
n = 3, edges = [[0,1,2],[0,2,5],[2,1,-4]], src = 0 | [0, 1, 5] | Through 2 is cheaper than direct: 5 − 4 = 1. |
n = 4, edges = [[0,1,1],[1,2,2],[2,3,-6],[3,1,3]], src = 0 | [] | 1 → 2 → 3 → 1 totals −1 and is reachable from 0. |
n = 4, edges = [[1,2,-1],[2,1,-1],[0,3,2]], src = 0 | [0, 1000000000, 1000000000, 2] | There is a negative cycle, but 0 cannot reach it. |
Constraints
- 1 ≤ n ≤ 500
- 0 ≤ edges.length ≤ 5000
- −10⁴ ≤ w ≤ 10⁴
Hints
Hint 1
Relax every edge, in any order, n − 1 times. A shortest path has at most n − 1 edges.
Hint 2
Never relax an edge out of a node whose distance is still infinite: ∞ plus a negative weight is still ∞.
Hint 3
After n − 1 rounds, try one more. If any edge still improves a distance, a negative cycle is reachable.
Where people lose marks
- Relaxing from a node at infinity: with a sentinel like 10⁹, adding a negative weight produces a "distance" below the sentinel for a node that was never reached.
- Reporting a negative cycle anywhere in the graph rather than only one reachable from the source.
- Running exactly n − 1 rounds and skipping the check round.
Dry run on 5,[[3,4,2],[2,3,1],[1,2,-2],[0,1,4],[0,2,5],[0,3,8],[1,3,6]],0
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6
Start: the source 0 is at 0, everything else at ∞. Edges are relaxed in the order they are listed.
-
Step 2 / 6
Round 1: 1: ∞ → 4 via 0; 2: ∞ → 5 via 0; 3: ∞ → 8 via 0.
-
Step 3 / 6
Round 2: 4: ∞ → 10 via 3; 3: 8 → 6 via 2; 2: 5 → 2 via 1.
-
Step 4 / 6
Round 3: 4: 10 → 8 via 3; 3: 6 → 3 via 2.
-
Step 5 / 6
Round 4: 4: 8 → 5 via 3.
-
Step 6 / 6
A check round: no edge can be improved, so there is no negative cycle and the distances are final.
How to think about it
Bellman–Ford: set the source to 0 and every other node to infinity, then relax every edge n − 1 times. After round k every node whose shortest path has at most k edges is correct, and without a negative cycle no shortest path needs more than n − 1 edges. If a round changes nothing, stop early.
A further round that still improves some distance means distances can fall for ever, which only a negative cycle allows. Because unreachable nodes stay at infinity and are never relaxed from, a negative cycle the source cannot reach never triggers the test, which is what the problem asks.
Complexity. Time O(n · m) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def bellman_ford(n, edges, src):
INF = 10**9
dist = [INF] * n
dist[src] = 0
for _ in range(n - 1):
changed = False
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]: # never relax from an unreached node
dist[v] = dist[u] + w
changed = True
if not changed:
break # nothing can change any more
for u, v, w in edges: # one more round: any improvement means a negative cycle
if dist[u] != INF and dist[u] + w < dist[v]:
return []
return dist#include <vector>
std::vector<long long> solve(int n, const std::vector<std::vector<int>>& edges, int src) {
const long long INF = 1000000000;
std::vector<long long> dist(n, INF);
dist[src] = 0;
for (int round = 0; round < n - 1; ++round) {
bool changed = false;
for (const auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
}
if (!changed) break; // nothing can change any more
}
for (const auto& e : edges) // a further improvement: negative cycle
if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return {};
return dist;
}class Solution {
public int[] bellmanFord(int n, int[][] edges, int src) {
final int INF = 1_000_000_000;
int[] dist = new int[n];
java.util.Arrays.fill(dist, INF);
dist[src] = 0;
for (int round = 0; round < n - 1; round++) {
boolean changed = false;
for (int[] e : edges) {
if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
}
if (!changed) break; // nothing can change any more
}
for (int[] e : edges) // a further improvement: negative cycle
if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return new int[0];
return dist;
}
}function bellmanFord(n, edges, src) {
const INF = 1e9;
const dist = new Array(n).fill(INF);
dist[src] = 0;
for (let round = 0; round < n - 1; round++) {
let changed = false;
for (const [u, v, w] of edges) {
if (dist[u] !== INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
}
if (!changed) break; // nothing can change any more
}
for (const [u, v, w] of edges) { // a further improvement means a negative cycle
if (dist[u] !== INF && dist[u] + w < dist[v]) return [];
}
return dist;
}fn solve(n: i64, edges: &[[i64; 3]], src: i64) -> Vec<i64> {
const INF: i64 = 1_000_000_000;
let n = n as usize;
let mut dist = vec![INF; n];
dist[src as usize] = 0;
for _ in 0..n.saturating_sub(1) {
let mut changed = false;
for e in edges {
let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
if dist[u] != INF && dist[u] + w < dist[v] {
dist[v] = dist[u] + w;
changed = true;
}
}
if !changed {
break; // nothing can change any more
}
}
let negative_cycle = edges.iter().any(|e| {
let (u, v) = (e[0] as usize, e[1] as usize);
dist[u] != INF && dist[u] + e[2] < dist[v]
});
if negative_cycle { Vec::new() } else { dist }
}import Data.List (foldl')
import qualified Data.Map.Strict as M
solve :: Int -> [[Int]] -> Int -> [Int]
solve n edges src
| any improves edges = [] -- a further improvement: negative cycle
| otherwise = [M.findWithDefault inf v final | v <- [0 .. n - 1]]
where
inf = 1000000000
start = M.singleton src 0
-- one round relaxes every edge; nodes absent from the map are unreached
relax d [u, v, w] = case M.lookup u d of
Just du | du + w < M.findWithDefault inf v d -> M.insert v (du + w) d
_ -> d
rounds k d
| k == 0 = d
| d' == d = d -- nothing changed: stop early
| otherwise = rounds (k - 1) d'
where d' = foldl' relax d edges
final = rounds (n - 1) start
improves [u, v, w] = case M.lookup u final of
Just du -> du + w < M.findWithDefault inf v final
Nothing -> FalseVariants to try
- Mark every node whose distance is −∞ (reachable from a negative cycle) instead of giving up.
- Find an arbitrage: given exchange rates, decide whether some cycle of trades multiplies money, using weights −log(rate).
- Cheapest flight with at most k stops: k + 1 rounds, each reading the previous round's distances.
Next problems
Shortest distances from one node
Return the shortest distance from a source to every node of a weighted directed graph: Dijkstra's algorithm with a heap.
Open the problem → Medium25 minTime for a signal to reach every node
Breadth-first search counts edges; when edges have travel times, a heap settles the nearest node first.
Open the problem → Medium25 minCheapest fare with at most k stops
Find the cheapest route that changes plane at most k times. Plain Dijkstra fails here; k + 1 rounds of Bellman-Ford do not.
Open the problem →Write a solution and run it against the real test table.
Keep going
Shortest distances from one node
Return the shortest distance from a source to every node of a weighted directed graph: Dijkstra's algorithm with a heap.
Open the problem → Medium25 minTime for a signal to reach every node
Breadth-first search counts edges; when edges have travel times, a heap settles the nearest node first.
Open the problem → Medium25 minCheapest fare with at most k stops
Find the cheapest route that changes plane at most k times. Plain Dijkstra fails here; k + 1 rounds of Bellman-Ford do not.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.