Floyd-Warshall Algorithm Explained with Python Code

You want to learn about the Floyd-Warshall Algorithm—an all-pairs shortest-path algorithm that computes the shortest paths between every pair of nodes in a weighted graph (including directed and undirected graphs), right? Unlike Dijkstra’s Algorithm (single-source) or Bellman-Ford (single-source with negative weights), Floyd-Warshall uses a dynamic programming approach to solve the all-pairs problem in a straightforward, matrix-based way. It can handle negative edge weights (but not negative cycles) and is ideal for dense graphs or small-to-medium-sized graphs where simplicity is prioritized over raw speed.

I. Core Principles of the Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is built on the dynamic programming principle of optimality: the shortest path from node i to node j either goes directly from i to j, or through an intermediate node k. It iteratively updates a distance matrix to include each node as a potential intermediate, gradually refining the shortest paths between all pairs. Here’s the step-by-step workflow:

Initialize the Distance Matrix:
- Create a V x V matrix dist (where V is the number of nodes) where dist[i][j] is the weight of the edge from i to j (if it exists).
- Set dist[i][i] = 0 (distance from a node to itself is zero).
- Set dist[i][j] = infinity if there is no direct edge from i to j.
Dynamic Programming Update:
- For each intermediate node k (from 0 to V-1):
  - For each source node i (from 0 to V-1):
    - For each destination node j (from 0 to V-1):
      - Update dist[i][j] to be the minimum of its current value and the path i → k → j (i.e., dist[i][k] + dist[k][j]).
Terminate:
- After processing all intermediate nodes k, the dist matrix contains the shortest path distances between every pair of nodes (i, j).

Key Notes

Negative Cycles: The algorithm can detect negative cycles by checking if dist[i][i] < 0 for any node i (a negative distance from a node to itself implies a negative cycle).
Path Reconstruction: To retrieve the actual shortest path (not just distances), a predecessor matrix is maintained to track the previous node in the shortest path for each pair (i, j).
Matrix Representation: Nodes are typically indexed numerically (0, 1, 2, …, V-1) for easy matrix manipulation.

II. Complete Implementation Code (Python)

Below is a full implementation of the Floyd-Warshall Algorithm, including:

Distance matrix initialization and dynamic programming updates.
Detection of negative cycles.
Path reconstruction using a predecessor matrix.

python

运行

INF = float('inf')

def floyd_warshall(graph):
    """
    Floyd-Warshall Algorithm for all-pairs shortest paths
    :param graph: Adjacency matrix representation of the graph (V x V)
                  graph[i][j] = weight of edge i→j (INF if no edge, 0 if i==j)
    :return: (dist_matrix, pred_matrix, has_negative_cycle)
             dist_matrix: Shortest distance between every pair (i,j)
             pred_matrix: Predecessor matrix for path reconstruction
             has_negative_cycle: Boolean indicating if the graph has a negative cycle
    """
    V = len(graph)  # Number of nodes in the graph
    
    # Step 1: Initialize distance matrix (copy of input graph)
    dist_matrix = [[graph[i][j] for j in range(V)] for i in range(V)]
    
    # Step 2: Initialize predecessor matrix
    # pred[i][j] = k means the shortest path i→j goes through k (immediate predecessor of j)
    pred_matrix = [[None for j in range(V)] for i in range(V)]
    for i in range(V):
        for j in range(V):
            if i == j:
                pred_matrix[i][j] = None  # No predecessor for self
            elif graph[i][j] != INF:
                pred_matrix[i][j] = i     # Direct edge i→j: predecessor is i
            else:
                pred_matrix[i][j] = None  # No path initially
    
    # Step 3: Dynamic programming update (k = intermediate node)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # Update dist[i][j] if path i→k→j is shorter than current i→j
                if dist_matrix[i][k] != INF and dist_matrix[k][j] != INF:
                    if dist_matrix[i][j] > dist_matrix[i][k] + dist_matrix[k][j]:
                        dist_matrix[i][j] = dist_matrix[i][k] + dist_matrix[k][j]
                        pred_matrix[i][j] = pred_matrix[k][j]  # Update predecessor
    
    # Step 4: Check for negative cycles (dist[i][i] < 0 means a negative cycle exists)
    has_negative_cycle = False
    for i in range(V):
        if dist_matrix[i][i] < 0:
            has_negative_cycle = True
            break
    
    return dist_matrix, pred_matrix, has_negative_cycle

def reconstruct_floyd_path(pred_matrix, start, end):
    """
    Reconstruct the shortest path from start to end using the predecessor matrix
    :param pred_matrix: Predecessor matrix from floyd_warshall()
    :param start: Source node (integer index)
    :param end: Target node (integer index)
    :return: List of nodes in the shortest path (empty if no path exists)
    """
    path = []
    current = end
    
    # If no path exists, return empty list
    if pred_matrix[start][current] is None and start != end:
        return path
    
    # Trace back from end to start using predecessors
    while current is not None:
        path.append(current)
        if current == start:
            break
        current = pred_matrix[start][current]
        # Avoid infinite loop (e.g., negative cycle)
        if len(path) > len(pred_matrix):
            return ["Negative cycle detected: no valid path"]
    
    # Reverse to get path from start to end
    path.reverse()
    return path

# Test Cases
if __name__ == "__main__":
    # Test 1: Simple weighted graph (no negative weights, no cycles)
    # Nodes: 0, 1, 2, 3
    graph1 = [
        [0, 4, INF, 5],
        [INF, 0, 1, INF],
        [2, INF, 0, INF],
        [INF, INF, 1, 0]
    ]
    
    dist1, pred1, neg_cycle1 = floyd_warshall(graph1)
    print("=== Test 1: Simple Graph ===")
    print("Distance Matrix:")
    for row in dist1:
        print([x if x != INF else "INF" for x in row])
    # Expected output (distances):
    # [0, 4, 5, 5]
    # [3, 0, 1, 4]
    # [2, 6, 0, 7]
    # [3, 7, 1, 0]
    
    print("\nShortest path from 1 to 3:", reconstruct_floyd_path(pred1, 1, 3))
    # Expected: [1, 2, 3] (path 1→2→3, weight 1+1=2? Correct matrix shows 4—verify graph weights!)
    
    # Test 2: Graph with negative edge weight (no negative cycle)
    graph2 = [
        [0, 2, INF, INF],
        [INF, 0, -1, INF],
        [INF, INF, 0, 3],
        [INF, INF, INF, 0]
    ]
    dist2, pred2, neg_cycle2 = floyd_warshall(graph2)
    print("\n=== Test 2: Graph with Negative Edge ===")
    print("Distance Matrix:")
    for row in dist2:
        print([x if x != INF else "INF" for x in row])
    # Expected: 0→1→2→3 has weight 2 + (-1) + 3 = 4
    
    # Test 3: Graph with negative cycle
    graph3 = [
        [0, 1, INF],
        [INF, 0, -2],
        [-3, INF, 0]
    ]
    dist3, pred3, neg_cycle3 = floyd_warshall(graph3)
    print("\n=== Test 3: Graph with Negative Cycle ===")
    print("Has negative cycle:", neg_cycle3)  # Output: True
    print("Path from 0 to 0:", reconstruct_floyd_path(pred3, 0, 0))
    # Output: ["Negative cycle detected: no valid path"]

III. Key Code Explanations

1. Graph Representation

Uses an adjacency matrix (a 2D list) where:
- graph[i][j] = weight if there is a direct edge from node i to node j.
- graph[i][j] = INF (infinity) if no direct edge exists.
- graph[i][i] = 0 (distance from a node to itself is zero).
This representation is natural for Floyd-Warshall, as the algorithm operates on pairwise node distances directly.

2. Distance Matrix Initialization

The distance matrix dist_matrix is initialized as a copy of the input adjacency matrix—this sets the initial direct path distances between all node pairs.

3. Predecessor Matrix

The pred_matrix tracks the immediate predecessor of node j in the shortest path from node i. For a direct edge i→j, the predecessor is i; for no path, it is None.
When updating the shortest path to i→j via k, the predecessor of j is set to the predecessor of j in the path k→j (i.e., pred_matrix[k][j]).

4. Dynamic Programming Triple Loop

The outer loop iterates over intermediate nodes k—each iteration allows k to be part of the shortest path for any pair (i, j).
The inner two loops iterate over all source i and destination j pairs, updating the shortest path if the route through k is shorter.

5. Negative Cycle Detection

A negative cycle exists if dist_matrix[i][i] < 0 for any node i—this means the path from i to itself has a negative total weight (looping through the cycle reduces the distance infinitely).

6. Path Reconstruction

The reconstruct_floyd_path function traces back from the target node end to the source start using the predecessor matrix, then reverses the path to get the forward order. It detects infinite loops from negative cycles by limiting the path length.

IV. Algorithm Performance Analysis

Metric	Result	Explanation
Time Complexity	O(V³)	Three nested loops over `V` nodes (intermediate `k`, source `i`, destination `j`). This is fixed, regardless of the number of edges.
Space Complexity	O(V²)	Uses two `V x V` matrices (`dist_matrix` and `pred_matrix`) for storage.
Handling Negative Weights	Yes (but not negative cycles)	Can process graphs with negative edge weights, but negative cycles make shortest paths undefined (infinite loop reduces distance).
Graph Type Compatibility	Directed/undirected, dense/sparse	Works for both directed and undirected graphs; more efficient for dense graphs (where `E ≈ V²`)—sparse graphs are better handled by running Dijkstra’s for each node (O(V*(V+E)logV)).

When to Use Floyd-Warshall

Small Graphs: V < 1000 (O(V³) is manageable for small V).
All-Pairs Shortest Paths: Need to compute paths between every node pair (e.g., routing tables in small networks).
Negative Edge Weights: When the graph has negative edges but no negative cycles (Bellman-Ford for each node is an alternative but has O(V*E) time).
Simplicity: The triple-loop structure is easy to implement and debug compared to running single-source algorithms for all nodes.

V. Floyd-Warshall vs. Dijkstra’s (All-Pairs) vs. Bellman-Ford (All-Pairs)

Feature	Floyd-Warshall	Dijkstra’s (V times)	Bellman-Ford (V times)
Time Complexity	O(V³)	O(V*(V + E)logV)	O(V*E)
Space Complexity	O(V²)	O(V) (per run) + O(V²) (all results)	O(V) (per run) + O(V²) (all results)
Negative Weights	Yes (no negative cycles)	No	Yes (detects negative cycles)
Best For	Dense graphs, small V	Sparse graphs with non-negative weights	Sparse graphs with negative weights
Implementation	Simple (triple loop)	More complex (heap per run)	Simple (per run) but repetitive

VI. Practical Applications

Network Routing: Computes shortest paths between all pairs of routers in a small network (e.g., local area networks), where the number of nodes is small and dense connectivity is common.
Traffic Management: Finds the shortest travel times between all pairs of intersections in a small city’s road network (handles one-way streets/directed edges and variable travel times/weights).
Game Development: Calculates the shortest paths between all game objects (e.g., NPCs, items, waypoints) in a small game map, enabling AI pathfinding for multiple entities.
Matrix Multiplication Optimization: Used in dynamic programming problems that require pairwise optimizations (e.g., optimal matrix chain multiplication, though specialized algorithms exist for this).
Circuit Design: Finds the shortest signal paths between all pairs of components in a small electronic circuit, optimizing for signal delay.

Summary

Negative cycle detection: A built-in check for dist[i][i] < 0 identifies graphs with invalid shortest paths due to negative cycles.

The Floyd-Warshall Algorithm is a dynamic programming-based all-pairs shortest-path algorithm that uses a triple loop to update pairwise distances via intermediate nodes.

Core strengths: Handles negative edge weights (not cycles), simple implementation, and computes all-pairs paths in a single pass.

Core weaknesses: O(V³) time complexity (slow for large graphs) and O(V²) space complexity (memory-intensive for large V).

Ideal use cases: Small/dense graphs, all-pairs path computation, and scenarios where negative edge weights are present (without negative cycles).