Floyd-Warshall Algorithm for All-Pairs Shortest Paths

When you need the shortest path between every pair of vertices — not just from a single source — Floyd-Warshall is the textbook answer. It runs in O(V³) time, fits in a clean triple loop, and handles negative edge weights (as long as there are no negative cycles).

The Core Idea

Floyd-Warshall uses a simple DP insight: for every pair of vertices (i, j), check whether routing through an intermediate vertex k gives a shorter path than the current best.

Let dist[i][j] be the shortest distance from i to j. For each intermediate vertex k, update:

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

By iterating k from 0 to V-1 as the outer loop, every possible intermediate vertex is considered.

Before considering k:
i -----(5)-----> j
After considering k:
i —(2)—> k —(1)—> j   total = 3 < 5  ✓ update!

Implementation in Python

def floyd_warshall(n, edges):
    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] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

edges = [(0, 1, 3), (0, 2, 8), (1, 2, 2), (2, 0, 5), (2, 3, 1), (3, 1, 7)]
result = floyd_warshall(4, edges)

for row in result:
    print([x if x != float('inf') else '∞' for x in row])
# [0, 3, 5, 6]
# ['∞', 0, 2, 3]
# [5, 7, 0, 1]  (2→0 via direct edge weight 5)
# ['∞', 7, 9, 0]

Path Reconstruction

To recover the actual path, maintain a next_node matrix. next_node[i][j] stores the first vertex on the shortest path from i to j.

def floyd_warshall_with_path(n, edges):
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0
        nxt[i][i] = i

    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]

    return dist, nxt

def reconstruct_path(nxt, u, v):
    if nxt[u][v] is None:
        return []
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path

Detecting Negative Cycles

A negative cycle exists if any diagonal entry becomes negative after running the algorithm:

def has_negative_cycle(dist):
    for i in range(len(dist)):
        if dist[i][i] < 0:
            return True
    return False

If dist[i][i] < 0, vertex i lies on a negative cycle — you can keep going around and reducing the total weight indefinitely.

Complexity Analysis

For sparse graphs with a single source, Dijkstra (O(E log V)) or Bellman-Ford (O(VE)) is faster. Floyd-Warshall wins when you need all pairs and V is small to moderate (under ~500).

When to Use Floyd-Warshall

• All-pairs shortest paths — the classic use case.
• Transitive closure — is vertex i reachable from vertex j? Replace min with OR and + with AND.
• Dense graphs — adjacency matrix is natural; Dijkstra’s edge-list approach gains less here.
• Small V — V³ is fine when V ≤ 400; beyond that, consider running Dijkstra from each source.

Interview Tips

• Mention that Floyd-Warshall is O(V³) regardless of edge count — it always considers all pairs through all intermediates.
• If the interviewer asks about negative weights, point out that Floyd-Warshall handles them but Dijkstra does not.
• For a single-source query, suggest Dijkstra first; only reach for Floyd-Warshall when asked about all pairs.
• The k loop must be the outermost — getting the loop order wrong is a common bug.
• Path reconstruction with the next matrix is a frequent follow-up; practice writing it from memory.