progress

~/problems / More shortest paths

Bellman-Ford with negative edges

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy basics ~10 min

Dijkstra breaks on negative edge weights; Bellman-Ford doesn't. It relaxes every edge, n - 1 times: a shortest path has at most n - 1 edges, and after round k every path of up to k edges is accounted for.

Implement bellman_ford(n, edges, src) for a directed graph on 0 .. n-1 with edges (u, v, w), w possibly negative:

  • Return dist, the shortest distance from src to each node (float("inf") if unreachable).
  • If a negative cycle is reachable from src, return None. Detect it with one extra round: if any edge still relaxes, there's one. Unreachable negative cycles don't matter.
bellman_ford(4, [(0, 1, 4), (0, 2, 5), (2, 1, -3), (1, 3, 2)], 0)
# [0, 2, 5, 4]           0 -> 2 -> 1 is cheaper than 0 -> 1

bellman_ford(3, [(0, 1, 1), (1, 2, -2), (2, 1, 1)], 0)
# None                   1 -> 2 -> 1 has total weight -1

1 <= n <= 300, up to 1000 edges, |w| <= 10^6.

Show hint

one round is for u, v, w in edges: dist[v] = min(dist[v], dist[u] + w), skipping u while dist[u] is infinite.

Topic: Bellman-Ford, Floyd-Warshall, 0-1 BFS. Negative edges, all-pairs, and deque BFS for 0/1 weights.

0:00
Ctrl ' run · Ctrl ↵ submit
esc