Bellman-Ford

The Idea

Dijkstra settles the nearest node and never looks back, which a negative edge can invalidate. Bellman-Ford refuses to settle anything. It just relaxes every edge, round after round, V-1 times — enough for the longest possible shortest path. One extra round that still improves something proves the graph has a negative cycle.

Real-World Example

A freight desk pricing routes where some legs carry a rebate, so a leg can cost less than nothing. Nearest-first pricing would lock in a quote before the rebate leg is seen. Sweeping every leg repeatedly keeps every quote provisional until the numbers stop moving.

The Code

edges = [("a", "b", 4), ("a", "c", 5), ("b", "c", -3), ("c", "d", 3)]
nodes = ["a", "b", "c", "d"]
dist = {n: float("inf") for n in nodes}
dist["a"] = 0

for _ in range(len(nodes) - 1):        # V-1 rounds is always enough
    for u, v, w in edges:
        if dist[u] + w < dist[v]:      # relax every edge, every round
            dist[v] = dist[u] + w

negative_cycle = any(dist[u] + w < dist[v] for u, v, w in edges)
print(dist)             # {'a': 0, 'b': 4, 'c': 1, 'd': 4}
print(negative_cycle)   # False

dist = {"a": 0, "b": 7, "c": float("inf")}
for u, v, w in [("a", "b", 2), ("b", "c", -5)]:
  if dist[u] + w < dist[v]:
      dist[v] = dist[u] + w
print(dist["b"], dist["c"])