Bellman-Ford

Time Complexity

Relax every edge times.

Invariant

• After iteration , if node is hops from on a shortest path from to , then .

Limitations

• Works for negative weights, but not negative weight cycles
  • Run Bellman-Ford for iterations, and check for estimate change in last iteration.