- Floyd-Warshall Algorithm is an algorithm for solving All Pairs Shortest path problem which gives the shortest path between every pair of vertices of the given graph.
- Floyd-Warshall Algorithm is an example of dynamic programming.
- The main advantage of Floyd-Warshall Algorithm is that it is extremely simple and easy to implement.
Create a |V| x |V| matrix // It represents the distance between every pair of vertices as given
For each cell (i,j) in M do-
if i = = j
M[ i ][ j ] = 0 // For all diagonal elements, value = 0
if (i , j) is an edge in E
M[ i ][ j ] = weight(i,j) // If there exists a direct edge between the vertices, value = weight of edge
M[ i ][ j ] = infinity // If there is no direct edge between the vertices, value = ∞
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if M[ i ][ j ] > M[ i ][ k ] + M[ k ][ j ]
M[ i ][ j ] = M[ i ][ k ] + M[ k ][ j ]
- Floyd Warshall Algorithm consists of three loops over all nodes.
- The inner most loop consists of only operations of a constant complexity.
- Hence, the asymptotic complexity of Floyd-Warshall algorithm is O(n3), where n is the number of nodes in the given graph.
When Floyd- Warshall Algorithm is used?
- Floyd-Warshall Algorithm is best suited for dense graphs since its complexity depends only on the number of vertices in the graph.
- For sparse graphs, Johnson’s Algorithm is more suitable.
PRACTICE PROBLEM BASED ON FLOYD-WARSHALL ALGORITHM-
Consider the following directed weighted graph-
Using Floyd-Warshall Algorithm, find the shortest path distance between every pair of vertices.
- Remove all the self loops and parallel edges (keeping the edge with lowest weight) from the graph if any.
- In our case, we don’t have any self edge and parallel edge.
Now, write the initial distance matrix representing the distance between every pair of vertices as mentioned in the given graph in the form of weights.
- For diagonal elements (representing self-loops), value = 0
- For vertices having a direct edge between them, value = weight of that edge
- For vertices having no direct edges between them, value = ∞
From step-03, we will start our actual solution.
To learn how to write these matrices step by step, Watch this video.
The four matrices are-
The last matrix D4 represents the shortest path distance between every pair of vertices.
Get more notes and other study material of Design and Analysis of Algorithms (DAA).
Watch video lectures by visiting our YouTube channel LearnVidFun.