Floyd Warshall Algorithm in Python

In this tutorial, we are going to learn about the Floyd Warshall algorithm and its corresponding code in Python. We are going to solve this problem using Dynamic Programming. If you don’t know what Dynamic Programing is then you can go through to the following otherwise you can look over it.

What is Dynamic Programming?

Dynamic Programming is a Computer Programming method that optimizes the overlapping problems in plain recursion. In this type of problem We mainly use the previous result to solve the next. So here we store the results in an array and then reuse it. As a result of this, the time complexity will lesser and overlapping of sub-problem will go away.

Floyd Warshall Algorithm

The Floyd Warshall Algorithm (also known as WFI Algorithm) is mainly a Shortest path algorithm that we can apply to find the shortest path in a weighted graph containing positive or negative weight cycle in a directed graph. The only condition is there should not be any negative cycles in this graph.

• At first, we initialize a graph matrix(square) in which the vertexes containing no edges will be marked as infinity and the graph containing self-loop will be marked as zero.
• The initialization matrix will be marked as k=0 and then we will run 3 for loops k=n nested with i=n nested with j=n. Where n is the number of vertexes.
• We update the values of thi=e distances in the final loop as dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j].
• When the loop terminates the final values of the dist matrix are the shortest path among all edges one to another.

Time Complexity: O(n^3) [for 3 ‘for’ loops]

Space Required: O(n^2) [ for the 2D matrix]

Floyd Warshall Algorithm: Python Code

Following is the Python code for the above algorithm:

# Python Program for Floyd Warshall Algorithm
INF = 99999
def floydWarshall(graph,n): #n=no. of vertex
    dist=graph
    for k in range(n):
        for i in range(n):
            for j in range(n): 
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j])
     return dist

 

The input and output for this code is shown below:

Also read: Finding time-complexity of algorithms in Python