Bellman-Ford finds the shortest distance from a single source vertex to every other vertex in a weighted directed graph, and it works even when some edge weights are negative.

Edge relaxation

Every edge (u, v) with weight w is repeatedly relaxed using the rule dist[v] = min(dist[v], dist[u] + w(u, v)). If going through u is shorter than the current best known distance to v, that distance — and the predecessor of v — is updated.

Why V−1 passes suffice

A shortest path that doesn't repeat a vertex visits at most V−1 edges. Each full pass over all edges guarantees at least one more edge of every shortest path is finalized, so after V−1 passes every shortest path (if the graph has no negative cycle) has fully propagated.

The extra V-th pass

Running one more pass after the required V−1 checks for negative cycles: if any distance can still improve, a negative-weight cycle reachable from the source exists, and no shortest path is well-defined for the vertices it touches.

Complexity

Bellman-Ford runs in O(V·E) time and O(V) space. It is slower than Dijkstra's O((V+E) log V), but unlike Dijkstra it tolerates negative weights and can detect negative cycles — Dijkstra's greedy choice breaks down as soon as a negative edge appears.