Python - Apply the Floyd-Warshall Algorithm for All-Pairs Shortest Path

The Floyd-Warshall algorithm is a versatile technique for finding the shortest path between all pairs of nodes in a weighted graph. It works for both directed and undirected graphs, handling negative edge weights (as long as there are no negative cycles). This algorithm is efficient for relatively small graphs. Here's an example:

Example - Finding All-Pairs Shortest Paths with Floyd-Warshall in Python:

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]

    # Initialize the distance matrix with direct edges
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] is not None:
                dist[i][j] = graph[i][j]

    # Update distances using intermediate vertices
    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

# Example usage:
inf = float('inf')
graph = [
    [0, 3, inf, 7],
    [8, 0, 2, inf],
    [5, inf, 0, 1],
    [2, inf, inf, 0]
]

all_pairs_shortest_paths = floyd_warshall(graph)
for row in all_pairs_shortest_paths:
    print(row)

In this example, we use the Floyd-Warshall algorithm to find the shortest paths between all pairs of nodes in a weighted graph. The graph variable represents the adjacency matrix, where inf indicates no direct edge between nodes.

The Floyd-Warshall algorithm is efficient for small to moderately sized graphs and can handle dense graphs with various edge weights. It's especially useful for solving problems that require knowledge of the shortest paths between all pairs of nodes, such as network routing or distance matrix computation.