How to implement Floyd-Warshall algorithm using Python?

How to implement Floyd-Warshall algorithm using Python?

Floyd-Warshall algorithm is a classic algorithm used to solve the shortest path problem from all source points to all destination points. It is a dynamic programming algorithm that can be used to deal with directed graphs or negative weight edge problems. This article will introduce how to use Python to implement the Floyd-Warshall algorithm and provide specific code examples.

The core idea of ​​the Floyd-Warshall algorithm is to gradually update the shortest path between nodes by traversing all nodes in the graph, using each node as an intermediate node. We can use a two-dimensional matrix to store the distance between nodes in the graph.

First, we need to define a function to implement the Floyd-Warshall algorithm. The following is a simple algorithm framework:

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

This code uses three nested loops to process each node in the graph. In each iteration, we find shorter paths by updating the distance matrix. Specifically, we will check whether the path from node i to node j can achieve a shorter distance through node k. If so, we update the value in the distance matrix.

Before using this function, we need to define a graph. The following is the definition of an example graph:

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

This example graph is an adjacency matrix representation of a directed graph. Among them, float('inf') means that the distance is infinite, which means there is no direct connection between the two nodes.

Below, we call the floydWarshall function, pass in the graph as a parameter, and print the final result:

result = floydWarshall(graph)
for row in result:
    print(row)

The complete code is as follows:

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

result = floydWarshall(graph)
for row in result:
    print(row)

Run the above code, you will get the following output:

[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]

The output result is a two-dimensional matrix representing the shortest path between any two nodes in the graph. For example, the value of result[0][2] is -2, which means that the shortest path distance from node 0 to node 2 is -2. If two nodes are unreachable, the distance is marked as infinity.

Through this example, we can clearly understand the implementation and use of the Floyd-Warshall algorithm. I hope this article can help you understand and apply this algorithm!

The above is the detailed content of How to implement Floyd-Warshall algorithm using Python?. For more information, please follow other related articles on the PHP Chinese website!