Graph Theory37 sections · 1633 units
Open in Course

When Bellman-Ford Wins

(Negative weights allowed)

Bellman-Ford works with negative edges. It relaxes all edges N1N-1 times to find shortest paths. It also detects negative cycles reachable from the source. If a negative cycle exists, shortest paths may not be defined.

Bellman-Ford tells you this happened by checking if any edge can still relax after N1N-1 iterations. Use Bellman-Ford when weights can be negative and you need single-source distances.