Bellman-Ford algorithm

A shortest-path algorithm that works even with negative edge weights by relaxing every edge V minus one times.

In more detail

After k rounds, every shortest path that uses at most k edges is correct, and no simple path needs more than V minus one edges. It costs O(V × E), slower than Dijkstra's algorithm. If a further round still improves a distance, the graph contains a negative cycle.

Related terms

Taught in

References