An algorithm for single-source shortest paths that can handle negative edge weights and detect negative cycles.
The Bellman-Ford algorithm is another method for finding the shortest paths from a single source vertex to all other vertices in a weighted graph. Its key advantage over Dijkstra's algorithm is its ability to handle graphs with negative edge weights. The algorithm is simpler in structure but generally slower. It works by relaxing all edges in the graph `V-1` times, where `V` is the number of vertices. A single relaxation pass over all edges updates the distance to each vertex `v` if a shorter path is found through some edge `(u, v)`. After `V-1` iterations, the algorithm is guaranteed to have found the shortest path for all vertices, provided there are no negative-weight cycles reachable from the source. The real power of Bellman-Ford comes in its ability to detect such cycles. After `V-1` iterations, a final pass over all edges is performed. If any distance can still be improved, it means a negative-weight cycle exists, as the path length can be decreased indefinitely by traversing the cycle. This feature is crucial in applications like arbitrage in financial markets. The time complexity of Bellman-Ford is O(V * E), which is higher than Dijkstra's, making it less suitable for graphs without negative edges.