Bellman-Ford Relaxation Loop and Cycle Detection

Bellman-Ford relaxes every edge n-1 times to settle all shortest paths; a single extra (n-th) pass that still relaxes an edge proves a negative cycle is reachable.