The idea
Relax every edge V-1 times. After V-1 rounds, all shortest paths are found. A V-th relaxation revealing shorter paths → negative cycle exists.
Advertisement
The algorithm
int[] dist = new int[n]; Arrays.fill(dist, INF);
dist[start] = 0;
for (int i = 0; i < n - 1; i++)
for (int[] edge : edges)
if (dist[edge[0]] + edge[2] < dist[edge[1]])
dist[edge[1]] = dist[edge[0]] + edge[2];
// Negative cycle check
for (int[] edge : edges)
if (dist[edge[0]] + edge[2] < dist[edge[1]])
throw new NegativeCycleException();Advertisement
Complexity
O(VE). Slower than Dijkstra's O(E log V).
When to use
Graphs with negative weights. Currency arbitrage detection. When negative-cycle detection matters.