Course contentsShow
← Computer Science
Lesson 996 of 2,87223. Shortest Path AlgorithmsFree lesson

Detecting Negative Cycles

Using diagonal entries in the distance matrix to identify the presence of negative-weight cycles.

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.