Floyd-Warshall Algorithm | Shortest Path Algorithm

Floyd-Warshall Algorithm-

 

  • 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.

 

Algorithm-

 

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

else

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 ]

 

Time Complexity-

 

  • 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-

 

Problem-

Consider the following directed weighted graph-

 

 

Using Floyd-Warshall Algorithm, find the shortest path distance between every pair of vertices.

 

Solution-

 

Step-01:

 

  • 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.

 

Step-02:

 

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 = 

 

 

Step-03:

 

From step-03, we will start our actual solution.

 

NOTE

  • Since, we have total 4 vertices in our given graph, so we will have total 4 matrices of order 4 x 4 in our solution. (excluding initial distance matrix)
  • Diagonal elements of each matrix will always be 0.

 

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.

Summary
Floyd-Warshall Algorithm | Shortest Path Algorithm
Article Name
Floyd-Warshall Algorithm | Shortest Path Algorithm
Description
Floyd-Warshall Algorithm is an algorithm for solving All Pairs Shortest path problem. Floyd-Warshall Algorithm example step by step. Floyd-Warshall Algorithm is an example of dynamic programming. Floyd-Warshall Algorithm best suited for dense graphs. The asymptotic complexity of Floyd-Warshall algorithm is O(n3).
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-