Dijkstra breaks as soon as an edge weight is negative. Bellman-Ford doesn't: it simply relaxes every edge, n - 1 times. A shortest path uses at most n - 1 edges, so after round k every path of at most k edges has been accounted for.
The graph is directed with nodes 0 .. n-1, and edges is a list of (u, v, w) where w may be negative. Implement bellman_ford(n, edges, src):
- Return a list
distof lengthnwith the shortest distance fromsrcto each node, andfloat("inf")for nodes that can't be reached. - If a negative cycle can be reached from
src(so distances could go down forever), returnNoneinstead. Detect it with one extra round: if any edge can still be relaxed, there is such a cycle.
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
Constraints: 1 <= n <= 300, up to 1000 edges, |w| <= 10^6. A negative cycle that src can't reach doesn't matter.
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); do n - 1 rounds, then one more pass that only checks whether anything would still improve.