Floyd-Warshall Algorithm

Analogy categoryAnalogies

Introduction

Floyd-Warshall solves the all-pairs shortest path problem: given a weighted directed graph, find the shortest distance between every pair of vertices simultaneously. Unlike running a single-source algorithm like Dijkstra from every vertex, Floyd-Warshall uses dynamic programming to build up the answer in a single unified process. It handles negative edge weights correctly, as long as the graph contains no negative-weight cycle, and its simplicity -- just three nested loops -- makes it a favorite for dense graphs or small-to-medium vertex counts.

🏏

Cricket analogy: Instead of calculating one batsman's best route to a century separately for every partnership (like running Dijkstra from each vertex), Floyd-Warshall computes every pair of batsmen's best combined run-scoring path simultaneously in one unified pass through the scorecard.

Algorithm/Syntax

python

def floyd_warshall(n, edges):
    """n: number of vertices (0..n-1). edges: list of (u, v, weight).
    Returns an n x n distance matrix; dist[i][j] = float('inf') if unreachable.
    """
    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)  # keep the cheapest parallel edge

    for k in range(n):          # intermediate vertex allowed
        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]

    return dist

Explanation

The core idea is dynamic programming over an expanding set of allowed intermediate vertices. dist[i][j] after considering vertices {0, ..., k} represents the shortest path from i to j that only passes through those vertices as intermediate stops. The recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) asks: is it shorter to go from i to j directly (without using k), or to route through k? By iterating k from 0 to n-1 and updating the entire matrix at each step, every possible intermediate vertex is eventually considered, and the matrix converges to true shortest paths. Because negative edges are simply values in the initial matrix, the algorithm naturally handles them -- but if a negative-weight cycle exists, some dist[i][i] will end up negative, signaling the graph has no well-defined shortest paths for vertices reachable through that cycle.

🏏

Cricket analogy: Considering whether a batting partnership's best total comes directly or via a third batsman rotating strike (intermediate vertex k) is the Floyd-Warshall recurrence: compare the direct partnership total against routing through k, and if a rotation loop keeps 'gaining' runs impossibly, that's a sign of a broken scoring cycle.

Example

python

def floyd_warshall_with_cycle_check(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] = min(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]

    has_negative_cycle = any(dist[i][i] < 0 for i in range(n))
    return dist, has_negative_cycle


# 4 vertices, includes a negative edge but no negative cycle
edges = [(0, 1, 3), (0, 2, 8), (0, 3, -4), (1, 3, 1), (1, 0, 4),
         (2, 1, 7), (3, 2, 6), (3, 0, 2)]
dist, neg_cycle = floyd_warshall_with_cycle_check(4, edges)
for row in dist:
    print(row)
# Row 0: [0, 1, -3, -4]  -- shortest paths from vertex 0 to all others
print('Negative cycle:', neg_cycle)  # False

Complexity

Time complexity is O(V^3) regardless of the number of edges, since the three nested loops each run V times. Space complexity is O(V^2) for the distance matrix (path reconstruction needs an additional O(V^2) predecessor matrix). This makes Floyd-Warshall efficient for dense graphs where E is close to V^2, but it becomes slower than running Dijkstra V times (O(V * E log V)) or Bellman-Ford V times on sparse graphs with many vertices.

🏏

Cricket analogy: With V teams in a round-robin tournament, computing every pairwise best-case result takes O(V^3) effort since three nested comparisons run per team-triple, and storing the full V-by-V results grid (plus a predecessor grid for how each result was reached) takes O(V^2) space — efficient when nearly every team has played every other, but wasteful for a sparse fixture list.

Key Takeaways

Floyd-Warshall computes shortest paths between all pairs of vertices in O(V^3) time and O(V^2) space.
It is a dynamic programming algorithm: dist[i][j] is refined by considering each vertex k as a potential intermediate stop.
It correctly handles negative edge weights, unlike Dijkstra.
A negative value on the diagonal (dist[i][i] < 0) after running indicates a negative-weight cycle.
Best suited to dense graphs or when all-pairs distances are needed; overkill for single-source queries on sparse graphs.

Practice what you learned

1. What is the time complexity of the Floyd-Warshall algorithm?

2. How does Floyd-Warshall detect the presence of a negative-weight cycle?

3. What does dist[i][k] + dist[k][j] < dist[i][j] represent in the core recurrence?

4. For which type of graph is Floyd-Warshall typically the best algorithmic choice?

Was this page helpful?

Union-Find and Disjoint Sets

Bellman-Ford Algorithm

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#FloydWarshallAlgorithm#Floyd#Warshall#Algorithm#Syntax#StudyNotes#SkillVeris