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 fromsrcto each node (float("inf")if unreachable). - If a negative cycle is reachable from
src, returnNone. 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.