🗺️ Bellman-Ford Algorithm — Shortest Paths with Negative Weights

Why does Bellman-Ford need V−1 passes?

Because the longest possible shortest path in a graph with V vertices (one that doesn't repeat a vertex) can have at most V−1 edges. Each full pass over every edge guarantees that at least one more edge along every shortest path becomes finalized, so after V−1 passes all shortest distances have fully propagated.

How does Bellman-Ford detect negative cycles?

After the required V−1 passes, the algorithm runs one extra pass over all edges. If any edge can still be relaxed — meaning a distance would still decrease — a negative-weight cycle reachable from the source must exist, since a valid shortest-path tree would already be stable by that point.

How does Bellman-Ford compare to Dijkstra's algorithm?

Both compute single-source shortest paths, but Dijkstra uses a greedy priority queue and requires non-negative weights, running in O((V+E) log V). Bellman-Ford relaxes every edge on every pass, tolerates negative weights, and can detect negative cycles, at the cost of a slower O(V·E) running time.

Can Bellman-Ford handle undirected graphs with negative edges?

No. Any undirected edge with a negative weight is equivalent to a two-vertex negative cycle (u→v and v→u), so Bellman-Ford would immediately flag it as a negative cycle. The algorithm is designed for directed graphs; negative weights only make consistent sense once edges have a direction.