Floyd-Warshall Algorithm with Python Implementation

The Floyd-Warshall algorithm is a classic algorithm used to find the shortest paths between all pairs of nodes in a weighted graph. It is particularly useful for solving problems where you need to determine the shortest paths between every pair of nodes in a graph, such as in network routing or urban planning. This blog will walk you through the Floyd-Warshall algorithm, its implementation in Python, and some practical examples.

Overview of the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a classic example of dynamic programming applied to graph theory. It efficiently computes the shortest paths between all pairs of nodes in a weighted graph—whether the graph is directed or undirected, as long as it doesn't contain negative cycles.

Rather than solving each pairwise shortest path separately, the algorithm incrementally improves the solution by introducing one intermediate node at a time. By checking whether a path from node i to node j can be shortened by passing through another node k, it repeatedly updates a distance matrix that eventually holds the shortest path lengths between all node pairs. This algorithm is applicable in a large number of scenarios including:

• Network Routing: Finding optimal paths for data transmission between all nodes in a network.

• Map Navigation Systems: Precomputing shortest paths between all locations to speed up real-time route suggestions.

• Social Network Analysis: Measuring degrees of separation or closeness between users.

• Transitive Closure: Identifying reachability between nodes in unweighted graphs.

• Urban Traffic Management: Calculating fastest routes between intersections for traffic signal optimization.

• Dependency Resolution: Determining build order and resolving dependencies in compilers or package managers.

• Game AI Pathfinding: Precomputing shortest paths between regions in strategy or simulation games.

• Telecommunication Networks: Optimizing call routing and network resource allocation.

  
  

The Floyd-Warshall algorithm is a foundational technique in graph algorithms and dynamic programming. Its ability to compute all-pairs shortest paths in a single pass makes it highly valuable in scenarios where distance information between every node pair is needed. While not optimal for extremely large graphs due to its time complexity, its clarity and completeness make it an essential tool in the algorithmic toolbox. Few of the key concepts in this algorithm are :

1. Distance Matrix

A 2D matrix dist[i][j] is used to track the shortest known distance from node i to node j. Initially, this matrix is populated with:

• The direct edge weights between nodes.

• Zeroes on the diagonal (dist[i][i] = 0 for all i).

• Infinity (∞) where no direct edge exists.

2. Intermediate Node

An intermediate node k serves as a potential "stepping stone" between any two nodes i and j. If going from i → k → j is shorter than the current path i → j, the algorithm updates the distance matrix accordingly.

3. Relaxation Process

The core of the algorithm involves triple nested loops over all node indices. Each iteration checks:

if dist[i][j] > dist[i][k] + dist[k][j]:
    dist[i][j] = dist[i][k] + dist[k][j]

This condition performs the relaxation step, ensuring that the shortest possible distance is always recorded. Following are the steps involved in this algorithm:

1. Initialization

• Construct a distance matrix dist with initial values.

• If there's an edge between i and j, set dist[i][j] to the edge's weight.

• Set dist[i][i] = 0 for all nodes.

• Use ∞ where no direct path exists.

  
  

2. Iterative Update (Relaxation)

• For every possible intermediate node k, iterate over all pairs of nodes (i, j).

• Update dist[i][j] if a shorter path is found through k.

  
  

3. Final Result

• After completing all iterations, dist[i][j] contains the shortest distance between every node i and node j.

• The result is a complete view of all-pairs shortest paths in the graph.

Python Implementation for Floyd-Warshall Algorithm

Let’s implement the Floyd-Warshall algorithm in Python. We’ll start by initializing the distance matrix, then perform the relaxation steps, and finally print the shortest paths.

# Number of vertices in the graph
V = 4

# Define infinity as a large enough value
INF = float('inf')

# Floyd-Warshall Algorithm
def floyd_warshall(graph):
    # Create a copy of the graph to store distances
    dist = [row[:] for row in graph]

    # Iterate through all possible intermediate vertices
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # If passing through vertex k gives a shorter path, update it
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# Example graph represented as an adjacency matrix
# graph[i][j] = weight from node i to node j
# INF represents no direct edge
graph = [
    [0,   5,   INF, 10],
    [INF, 0,   3,   INF],
    [INF, INF, 0,   1],
    [INF, INF, INF, 0]
]

# Run the algorithm
shortest_paths = floyd_warshall(graph)

# Display the result
print("Shortest distance matrix:")
for row in shortest_paths:
    print(["∞" if x == INF else x for x in row])

Output:
Shortest distance matrix:
[0, 5, 8, 9]
['∞', 0, 3, 4]
['∞', '∞', 0, 1]
['∞', '∞', '∞', 0]

In this Python implementation of the Floyd-Warshall algorithm, we define a graph using an adjacency matrix where graph[i][j] represents the weight of the edge from node i to node j, and float('inf') (infinity) is used to denote the absence of a direct edge. The algorithm works by initializing a distance matrix dist as a copy of the input graph and then applying three nested loops. The outermost loop picks an intermediate node k, and the inner loops iterate over every possible pair of source i and destination j. For each pair, the algorithm checks if the path from i to j can be shortened by going through k. If it can, the distance matrix is updated. After all iterations, the matrix contains the shortest distances between every pair of nodes. The final result is printed, replacing infinite values with a symbol (∞) for better readability. This implementation is clean, easy to understand, and demonstrates the algorithm's core principle of dynamic programming for solving all-pairs shortest path problems.

Conclusion

The Floyd-Warshall algorithm is a powerful and versatile tool for computing the shortest paths between all pairs of nodes in a weighted graph. Its foundation in dynamic programming ensures that the algorithm systematically explores all possible paths, guaranteeing accurate results even in the presence of negative edge weights—provided there are no negative cycles. The method’s simplicity and elegance make it particularly appealing for educational purposes, prototyping, and solving dense graph problems.

While its cubic time complexity of O(V³) makes it less suitable for very large-scale networks, it performs efficiently on small to medium-sized graphs and remains highly relevant in domains where full path visibility is critical. These include network routing, transportation systems, urban planning, dependency resolution in compilers, and social network analysis.

Moreover, the Python implementation is easy to understand and extend, allowing developers to incorporate features like path reconstruction, cycle detection, or real-time graph updates. As such, Floyd-Warshall is not just a theoretical algorithm, but a practical and adaptable solution for a wide range of computational challenges involving graph-based data.