Page 80 - Data Structures Handout_Neat

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