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: