**Floyd Warshall Algorithm-**

- Floyd Warshall Algorithm is a famous algorithm.
- It is used to solve All Pairs Shortest Path Problem.
- It computes the shortest path between every pair of vertices of the given graph.
- Floyd Warshall Algorithm is an example of dynamic programming approach.

**Also Read-** **Shortest Path Problem**

**Advantages-**

Floyd Warshall Algorithm has the following main advantages-

- It is extremely simple.
- It is easy to implement.

**Algorithm-**

Floyd Warshall Algorithm is as shown below-

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 the nodes.
- The inner most loop consists of only constant complexity operations.
- Hence, the asymptotic complexity of Floyd Warshall algorithm is O(n
^{3}). - Here, 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.
- This is because its complexity depends only on the number of vertices in the given 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 lowest weight edge) from the graph.
- In the given graph, there are neither self edges nor parallel edges.

**Step-02:**

- Write the initial distance matrix.
- It represents the distance between every pair of vertices in the form of given weights.
- For diagonal elements (representing self-loops), distance value = 0.
- For vertices having a direct edge between them, distance value = weight of that edge.
- For vertices having no direct edge between them, distance value = ∞.

Initial distance matrix for the given graph is-

**Step-03:**

Using Floyd Warshall Algorithm, write the following 4 matrices-

To learn how to write these matrices, watch this video **here**.

The last matrix D_{4} represents the shortest path distance between every pair of vertices.

**Remember-**

- In the above problem, there are 4 vertices in the given graph.
- So, there will be total 4 matrices of order 4 x 4 in the solution excluding the initial distance matrix.
- Diagonal elements of each matrix will always be 0.

To gain better understanding about Floyd Warshall Algorithm,

**Next Article-** **Knapsack Problem**

Get more notes and other study material of **Design and Analysis of Algorithms**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.