Page 80 - Data Structures Interactive Book
P. 80
8.4.2 Bellman-Ford Algorithm
The Bellman-Ford algorithm is designed to handle graphs with negative edge weights,
something Dijkstra’s algorithm cannot manage. It works by repeatedly relaxing all edges,
gradually improving the shortest path estimates. After − 1iterations (where is the number
of vertices), the shortest paths are guaranteed to be found if no negative cycles exist. A final
iteration checks for negative cycles: if any distance can still be improved, a negative cycle
exists.
Step-by-step process:
1. Initialize distances: source = 0, others = infinity.
,
2. Repeat − 1times: for each edge ( ), update dist[v] if dist[u] + weight < dist[v].
3. Check for negative cycles by performing one more relaxation.
Example in C++:
This implementation shows how Bellman-Ford can detect negative cycles while
computing shortest paths.
80
