The All Pair Shortest Path Problem is about finding a path between each and every vertex to all other vertices in a graph such that the total distance between them is minimum.
The Floyd Warshall Algorithm is used for solving the All Pairs Shortest Path problem. We implement this by finding the shortest path between every pair of vertices in a given weighted directed graph.
- There exists five offices in five different cities.
- The cost of travel between each pair of cities is known.
- We have to find the cheapest way to reach each office from every other office.
Floyd Warshall Algorithm to solve All Pair Shortest Path Problem
The Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm can be applied to both directed and undirected weighted graphs.
However, the Floyd-Warshall Algorithm does not work with graphs having negative cycles. Floyd-Warshall Algorithm follows the dynamic programming approach to find the shortest paths.
Note: A graph can have positive as well as negatively weighted edges. A negative cycle is one in which the overall sum of the cycle becomes negative.
Implementation of Floyd-Warshall Algorithm
For the implementation of the Floyd-Warshall Algorithm, we create the
floydWarshall method that takes two parameters as input – the number of vertices and a reference to the graph data structure.
The Floyd-Warshall Algorithm is based on the following steps:
- We are given a weighted directed or undirected graph.
- We create a matrix of size
N*Nwhere N is the number of vertices of the graph. Let this matrix be called
- The value of the
A[i][j]cell is the weight of the direct path between the ith and jth nodes of the graph. If no direct path exists between two vertices, set their distance infinity for the moment.
- Now we iterate over each pair of nodes in the matrix and reduce the paths to the shortest distance.
- This process is repeated until all pairs of nodes are assigned their desiredd path lengths.
#Function to implement Floyd-Warshall Algorithm INF = 9999 def printSolution(numOfVertices, distance): for i in range(numOfVertices): for j in range(numOfVertices): if(distance[i][j] == INF): print("INF", end=" ") else: print(distance[i][j], end=" ") print(" ") def floydWarshall(numOfVertices, G): distance = G for k in range(numOfVertices): for i in range(numOfVertices): for j in range(numOfVertices): distance[i][j] = min( distance[i][j], distance[i][k]+distance[k][j]) printSolution(numOfVertices, distance) G = [[0, 8, INF, 1], [INF, 0, 1, INF], [4, INF, 0, INF], [INF, 2, 9, 1] ] floydWarshall(4, G)
Time and Space Complexity
The time complexity for the Floyd-Warshall Algorithm is O(V^3) because we use three nested for loops, each iterating over all the vertices of the graph. The space complexity is O(V^2) because we store all pairs of nodes in a temporary matrix.
BFS vs Dijkstra vs Bellman-Ford vs Floyd-Warshall
Graph Type BFS Dijkstra Bellman-Ford Floyd-Warshall Unweighted-undirected OK OK OK OK Unweighted-directed OK OK OK OK Positive-weighted-undirected X OK OK OK Positive-weighted-directed X OK OK OK Negative-weighted-undirected X OK OK OK Negative-weighted-directed X OK OK OK Negative Cycle X X OK X