Floyd-Warshall Algorithm in Python

Introduction

An approach for determining the shortest path between each pair of vertices in a weighted graph is called the Floyd-Warshall approach. Both directed and undirected weighted graphs can be used using this approach. However, it is ineffective for graphs with negative cycles, in which the total of all the edges is negative. Because of its versatility, the method can be used in various industries, including social network analysis, network routing, and transportation.

When utilizing the algorithm, diagonal elements are set to zero, and a distance matrix is initialized with direct edge weights. Next, it updates the distance matrix with the shortest pathways by iteratively considering each vertex as a possible intermediate. Until the matrix has all of the shortest distances between pairings, this process is repeated for each vertex. When applied to dense graphs with a few vertices, the algorithm's time complexity of O(V^3) indicates an efficient method. However, when there are negative cycles in the graph, it is less helpful in determining the shortest pathways that come from a single source.

How It Works?

To determine the shortest path between each pair of vertices, use the following procedures.

Make a matrix A0 with n vertices, where n is the matrix's dimension. The index values for the row and the column are i and j, respectively. The graph's vertices are i and j.

Every cell A[i][j] contains the length of time between the ith and jth vertices. The cell remains at infinity if there is no path connecting the ith and jth vertices.

Next, use matrix A0 to construct matrix A1. The first row and column's items are kept exactly as they are. This is how the remaining cells get filled.

Let k represent the vertex that sits in between the source and the destination on the shortest path. K is the initial vertex in this stage. If (A[i][j] > A[i][k] + A[k][j]), then A[i][j] is filled with (A[i][k] + A[k][j]).

In other words, the cell is filled with A[i][k] + A[k][j] if the direct distance between the source and the destination is larger than the path through the vertex k.

K is vertex 1 in this step. Through this vertex k, we compute the distance between the source and destination vertices.

For instance, Regarding A1[2, 4], the distance directly between vertex 2 and vertex 4 is 4, and the total distance between vertex 2 and vertex 4 via vertex (that is, from vertex 2 to 1 and from vertex 1 to 4) is 7. A0[2, 4] is filled with 4 since 4 < 7.

In the same way, A1 is used to make A2. The items in the second row and second column remain original.

K is the second vertices in this stage, or vertex 2. The steps that remain are the same as those in step 2.

Similarly, A3 and A4 is also created.

For every pair of vertices, the shortest path is shown in A4.

Algorithm

It functions by progressively refining a preliminary approximation of the shortest paths connecting vertices. The Floyd-Warshall algorithm consists of the following steps:

Initialization:

Make a matrix that shows the shortest paths between each pair of vertices. Set the initial values of this matrix according to the graph's direct edge weights. Set distance[i][j] to the edge's weight if there is one between vertices i and j. If there are no direct edges, set distance[i][j] to a significant number or infinity. Since there is always a zero distance between a vertex and itself, you should also set distance[i][i] to 0 for all vertices.

Iteration:

Think of each vertex 'k' in the network as a possible vertice that could be used as an intermediary on a path between vertices 'i' and 'j'.

Update the distance matrix as follows for each pair of vertices (i, j):

Minus distance[i][j], distance[i][k] + distance[k][j] equals distance[i][j].

For each of the vertices "k," repeat this process. Through this approach, the estimates of the shortest paths between every pair of vertices will be improved iteratively.

Repeat Iteration:

Till you've thought of every potential intermediate, repeat the iteration phase for all vertices, treating each vertex as a possible intermediate. This guarantees that the algorithm investigates every potential path, and the distance matrix is updated appropriately.

Final Result:

Once every cycle is finished, the shortest pathways between every pair of vertices will be found in the distance matrix.

The distance matrix should have converged to the accurate shortest distances between every pair of vertices, and the procedure is regarded as complete when all vertices have been treated as intermediates. V^3, or the number of vertices in the graph, is the temporal complexity of the Floyd-Warshall method.

Example 1:

V = 4

INF = 999

def floyd_warshall(G):

    dist = list(map(lambda i: list(map(lambda j: j, i)), G)) for k in range(V):

        for i in range(V):

            for j in range(V):

                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    print_solution(dist)

def print_solution(dist):

    for i in range(V):

        for j in range(V):

            if(dist[i][j] == INF):

                print("INF", end=" ")

            else:

                print(dist[i][j], end="  ")

        print(" ")

G = [[0, 3, INF, 5],

         [2, 0, INF, 4],

         [INF, 1, 0, INF],

         [INF, INF, 2, 0]]

floyd_warshall(G)

Output

0  3  7  5  

2  0  6  4  

3  1  0  5  

5  3  2  0  

>

Explanation

The Floyd-Warshall technique is implemented in the accompanying Python code to determine the shortest paths between every pair of vertices in a directed graph. An adjacency matrix, G[i][j], reflects the weight of the edge from vertex i to vertex j in the graph. By taking into account every potential intermediary vertex, the algorithm iteratively updates the distance matrix dist. The graph's edge weights are used to initialize the distance matrix, and "INF" (a big value) is assigned to represent infinite distances for vertices that are not adjacent.

The floyd_warshall function calculates the shortest path between i and j by iteratively going through all three vertices—i, j, and k—possibly using k as an intermediary. The resultant distance matrix is shown using the print_solution function. "INF" is written if there is no path connecting vertices i and j.

In the example given, the code considers INF as an indication of infinite distance when there isn't a direct edge and finds and publishes the shortest pathways between vertices in a graph with four vertices.

Example 2

def floyd_warshall(graph):

    V = len(graph)

    distance = [[float('inf')] * V for _ in range(V)]

    for i in range(V):

        distance[i][i] = 0

    for u, v, w in graph:

        distance[u][v] = w

    for k in range(V):

        for i in range(V):

            for j in range(V):

                if distance[i][j] > distance[i][k] + distance[k][j]:

                    distance[i][j] = distance[i][k] + distance[k][j]

    return distance

if __name__ == "__main__":

    graph = [

        (0, 1, 3),

        (0, 2, 6),

        (1, 2, 2),

        (1, 3, 9),

        (2, 3, 1),

        (3, 0, 4),

        (3, 1, 7)

    ]

 result = floyd_warshall(graph)

 for row in result:

        print(row)

Output

[0, 3, 5, 6, inf, inf, inf]

[7, 0, 2, 3, inf, inf, inf]

[5, 8, 0, 1, inf, inf, inf]

[4, 7, 9, 0, inf, inf, inf]

[inf, inf, inf, inf, 0, inf, inf]

[inf, inf, inf, inf, inf, 0, inf]

[inf, inf, inf, inf, inf, inf, 0]

>

Explanation

The source vertex (u), destination vertex (v), and weight of the edge connecting them (w) are the three values that each tuple in an input graph represented as a list of tuples includes. This function is called the floyd_warshall function.

The shortest distances between every pair of vertices are represented by the distance matrix, which is initialized. Except the diagonal entries, which are initially set to zero since the shortest path between a vertex and itself is always zero, all entries are initially set to infinity.

Next, using the edge information provided, the function updates the associated entries in the distance matrix by adding direct edge weights from the graph.

The triple-nested loop is the central component of the Floyd-Warshall algorithm. Vertex k is considered a possible intermediary in the path from vertex i to vertex j, and iteratively searches through all vertices (k, i, and j) to identify shorter courses. The matrix is updated if a more straightforward path is discovered.

The shortest pathways between each pair of vertices are contained in the distance matrix once the algorithm has been run.

To show the shortest paths and the distances between them, the code prints the distance matrix that is produced.

Conclusion

A vital tool for determining the shortest paths between every pair of vertices in a weighted, directed graph is the Floyd-Warshall method. It can handle graphs with both positive and negative edge weights (provided no negative cycles exist), and it is durable and flexible. By considering every potential path in a single run, this method guarantees completeness and offers a complete solution. But for large graphs, its O(V^3) time complexity—where V is the number of vertices—may make it less effective. Despite this, it continues to be helpful when determining the all-pairs shortest path is crucial, making it an essential algorithm in domains including geographic information systems, network routing, and transportation.