Detecting Negative Cycles
What You'll Learn
You'll learn how to use the diagonal entries of Floyd-Warshall's distance matrix to detect negative-weight cycles in a graph.
The Core Idea
After running Floyd-Warshall, the distance matrix tells you the shortest path cost between every pair of vertices. But there's a clever trick hidden in plain sight: check the diagonal.
The diagonal entry dist[i][i] represents the shortest path from vertex i back to itself. In a graph without negative cycles, this should always be 0 (or remain 0 from initialization)—the cheapest way to "go nowhere" is to stay put.
However, if dist[i][i] becomes negative, it means there's a way to start at vertex i, follow some edges, return to i, and end up with a negative total cost. That's the definition of a negative cycle involving vertex i.
Why This Works
Floyd-Warshall tries all possible intermediate vertices when computing shortest paths. If a negative cycle exists, the algorithm will eventually discover a path from i to i with negative cost by routing through the cycle. Since Floyd-Warshall finds shortest paths, it picks this negative-cost loop.
How to Check
After Floyd-Warshall completes all iterations:
for i from 0 to V-1:
if dist[i][i] < 0:
return "Negative cycle detected"
return "No negative cycles"
Analogy
Imagine tracking your bank balance: starting at $0, you take a round trip through several transactions and return home with more money than you started with (negative debt). That's impossible in honest finance—and it signals something's broken (a negative cycle) in your graph.
Key Takeaway: After Floyd-Warshall, any negative value on the diagonal (dist[i][i] < 0) proves the graph contains a negative-weight cycle.