Floyd Warshall Algorithm Dynamic Programming

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³).
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₄ 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,

Watch this Video Lecture

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.

Tag: Floyd Warshall Algorithm Dynamic Programming

Floyd Warshall Algorithm | Example | Time Complexity