Definition

Bellman-Ford algorithm finds shortest distances from a single source to all other vertices. Unlike Dijkstra, it can handle negative edge weights and detect negative cycles.

Key Characteristics

• ✓Negative Weight Handling: Correctly computes shortest paths even with negative edges.
• ✓V-1 Iterations: Relaxing all edges V-1 times guarantees shortest paths.
• ✓Negative Cycle Detection: If updates occur in the V-th iteration, a negative cycle exists.

Time Complexity