Explain the Bellman-Ford Algorithm.

Explain the Bellman-Ford Algorithm.

Approach: Describe a shortest path algorithm that can handle negative weights.

An algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted digraph. Unlike Dijkstra, it can handle negative edge weights and detect negative cycles by relaxing all edges V-1 times.

Follow-up: What is the result of the V-th relaxation?

Key concepts: relaxation, negative cycles, O(VE).