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

Handling Negative Edge Weights

How Floyd-Warshall correctly handles negative weights and when it works versus fails.

Handling Negative Edge Weights

What you'll learn: How Floyd-Warshall correctly handles negative edge weights and when it works versus when it fails.

Why Floyd-Warshall Handles Negatives Well

Unlike Dijkstra's algorithm (which breaks with negative edges), Floyd-Warshall naturally handles negative edge weights because it doesn't rely on a greedy "commit once" strategy. Instead, it systematically considers all possible intermediate paths, allowing it to discover shorter routes even when they involve negative-weight edges.

Think of it like comparing prices: Dijkstra assumes prices only get higher as you add items (positive weights), so it locks in the first "good deal" it finds. Floyd-Warshall, however, checks every combination of intermediate stops, so even if a detour includes a discount (negative weight), it will eventually discover that saving.

When Floyd-Warshall Works

Floyd-Warshall correctly computes shortest paths when:

  • The graph has negative edge weights
  • There are no negative weight cycles (cycles whose total weight is negative)

The algorithm will find the optimal path using negative edges to reduce total distance, just as it would with positive edges.

When Floyd-Warshall Fails

If the graph contains a negative weight cycle reachable between two vertices, the shortest path is undefined (you could loop infinitely, making the distance approach negative infinity). Floyd-Warshall can detect this condition: after completing all iterations, check if any vertex has dist[i][i] < 0. If so, vertex i is part of a negative cycle.

Key Takeaway: Floyd-Warshall correctly handles negative edge weights by exhaustively checking all paths, but it cannot produce meaningful shortest paths when negative weight cycles exist—though it can detect their presence by checking the diagonal of the distance matrix.