Floyd-Warshall Algorithm

Floyd's or Floyd-Warshall Algorithm is used to find all pair shortest path for a graph. 

This algorithm works for weighted graph having positive and negative weight edges without a negative cycle.

Problem

Consider the following weighted graph.

Our task is to find the all pair shortest path for the given weighted graph.

Steps

Step 1: Remove all the loops.

Note! Any edge that starts and ends at the same vertex is a loop.

Step 2: Remove all parallel edges between two vertices leaving only the edge with the smallest weight.

Step 3: Create a distance and sequence table.

How we will proceed

• To find the shortest path between any two nodes we will draw two tables namely, Distance Table (D) and Sequence Table (S).
• We can also refer these tables as matrix.
• The Distance table (D) will hold distance between any two vertices.
• The Sequence table (S) will hold the name of the vertices that will help in finding the shortest path between any two vertices.
• If a graph has k vertices then our table D and S will have k rows and k columns.
• We will use the iterative method to solve the problem.

Notations we will be using

k = Iteration number
Dk = Distance table in kth iteration
Sk = Sequence table in kth iteration
dij = The distance between vertex i and j

There are 4 vertices in the graph so, our tables (Distance and Sequence) will have 4 rows and 4 columns.

Distance table D

This table holds the weight of the respective edges connecting vertices of the graph. 

So, if there in an edge u --> v connecting vertex u to vertex v and having weight w then we will fill the distance table D[u][v] = w. 

If there is no edge connecting any two vertex u to v then in that case we will fill D[u][v] = INFINITY.

From the graph above we will get the following distance table.

INF means INFINITY

Sequence table S

This table holds the vertex that will be used to find the shortest path to reach from vertex u to vertex v.

From the graph above we will get the following sequence table.

INF means INFINITY

Important Condition

We will fill the cell Cij in distance table Dk using the following condition.

Is dij > dik + dkj [in distance table Dk-1]
If YES then fill the cell Cij in Dk table with the value dik + dkj of Dk-1 table
If NO then fill the cell Cij in Dk table with the value dij of Dk-1 table
where
i = row number
j = column number
k = iteration number
i.e., we will always fill the cell Cij in Dk table with the smallest value.

Note! 

If a graph has N vertices then we will be iterating N times.

The graph has 4 vertices so, we will be iterating 4 times.

Solution

After completing the 4 iterations we will get the following distance array.

And the following sequence table

And the required shortest paths.

Time complexity

The time complexity of Floyd's or Floyd-Warshall algorithm is O(V3).