Graph Algorithms7 min read

Floyd-Warshall

Find shortest paths between every pair of cities in one sweep
time:\(O(V^3)\)space:\(O(V^2)\)handles:Negative weights (not negative cycles)

Imagine you run an airline and want to know the cheapest fare between every pair of cities. You could run Dijkstra from each city, but here's a more elegant approach: ask, city by city, "Does flying via city K make any trip cheaper?"

Start with direct flight prices. Then ask: "Does routing through city 1 make any trip cheaper?" Update prices. Then: "Does routing through city 2 make any trip cheaper?" Update again. After you've considered every city as a potential layover, every entry in your price table is the true cheapest fare.

That's Floyd-Warshall — an all-pairs shortest path algorithm built on a beautifully simple DP idea.

The DP Formulation

Define dist[i][j] as the shortest path from i to j. Initially:

  • dist[i][j] = weight(i,j) if a direct edge exists
  • dist[i][i] = 0
  • dist[i][j] = ∞ otherwise

The key recurrence — run for each intermediate vertex k from 1 to V:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

In plain English: "Is going from i to j via k cheaper than any route we've found so far?" After the outer loop completes all V values of k, every pair (i, j) holds the globally optimal answer.

Why In-Place Updates Are Safe

The 3D formulation dp[k][i][j] reduces to a 2D array. Why can you update in-place? When processing intermediate vertex k, the values dist[i][k] and dist[k][j] don't change during the k-th iteration — they represent paths using intermediates {1..k−1}, which are already optimal and don't route through k as an intermediate (routing through k to get to k would only add cost). So updating dist[i][j] in place using these values is always correct.

Detecting Negative Cycles

After running Floyd-Warshall, check the diagonal. If dist[i][i] < 0 for any vertex i, there's a negative cycle passing through i. The trivial path from i to i costs 0; if it went negative, the algorithm found a cycle with negative total weight. Any shortest path that routes through a negative cycle is undefined (infinitely cheap).

Transitive Closure

Replace min/+ with OR/AND (using boolean values) to compute whether each pair (i, j) is connected at all. This transitive closure variant runs in \(O(V^3)\) and answers reachability queries for all pairs in one sweep.

When to Use Floyd-Warshall vs. Dijkstra

For all-pairs shortest paths on a dense graph (E ≈ \(V^2\)) or when negative weights exist (use Bellman-Ford for single-source), Floyd-Warshall's \(O(V^3)\) often wins. On a sparse graph with only positive weights, running Dijkstra from every source costs \(O(V · (V+E)\) log V), which can be much better. The crossover is roughly when E ≪ \(V^2\).

Note: Three nested for loops — k, then i, then j. The outer loop k is the intermediate city. The order matters: k must be the outermost. If you accidentally put k inside, you get wrong answers.

Floyd-Warshall All-Pairs Shortest Path

def floyd_warshall(n, edges):
    """
    n: number of vertices (0-indexed)
    edges: list of (u, v, weight)
    Returns dist[i][j] = shortest path from i to j, or None if negative cycle.
    """
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)


    for k in range(n):           # intermediate vertex
        for i in range(n):       # source
            for j in range(n):   # destination
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]


    # Check for negative cycles
    for i in range(n):
        if dist[i][i] < 0:
            return None  # negative cycle
    return dist


# 4 cities, 0-indexed
edges = [(0,1,3),(0,3,7),(1,0,8),(1,2,2),(2,0,5),(2,3,1),(3,0,2)]
dist = floyd_warshall(4, edges)
for i in range(4):
    for j in range(4):
        val = dist[i][j] if dist[i][j] != float('inf') else '∞'
        print(f"{i}->{j}: {val}", end='  ')
    print()
Output
0->0: 0  0->1: 3  0->2: 5  0->3: 6  
1->0: 7  1->1: 0  1->2: 2  1->3: 3  
2->0: 5  2->1: 8  2->2: 0  2->3: 1  
3->0: 2  3->1: 5  3->2: 7  3->3: 0

Complexity

✈️ All-pairs shortest pathThree nested loops over k, i, j — practical for V up to ~1000
Cubic in vertices\(O(V^3)\)
💾 SpaceOne distance for every pair; 2D array sufficient after space optimization
Quadratic in vertices\(O(V^2)\)
🔍 Negative cycle detectionIf dist[i][i] < 0 for any i, a negative cycle passes through i
Free — check after main loop\(O(V)\)
🆚 Dijkstra × V sources (sparse)For sparse non-negative graphs, running Dijkstra from every vertex beats Floyd-Warshall
Often faster on sparse graphs\(O(V·(V+E)\) log V)

Quick check

What does dist[i][j] represent after Floyd-Warshall completes?

Continue reading

Bellman-Ford & SPFA
Handle negative weights and catch negative cycles
→
Dijkstra's Algorithm
Always extend the cheapest road first — GPS navigation for graphs
→