Core idea
Bellman-Ford relaxes all edges V-1 times, where V is the number of vertices.
Unlike Dijkstra, it correctly handles negative weight edges.
A final extra pass over all edges detects negative weight cycles.
If any distance still improves in the final pass, a negative cycle exists.
How it works
- Set distance to source as 0 and all other distances to infinity.
- Repeat V-1 times: for every edge (u, v, w), if dist[u] + w < dist[v], update dist[v].
- Run one more pass over all edges.
- If any distance improves, a negative cycle is present in the graph.