Description: The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph with no negative-weight cycles using Floyd Warshall Algorithm.

 

The above diagram is negative-weight cycle with total weight -1.

Eg:

Input:

graph[][] =          { {0, 5, INF, 8},

                              {INF, 0, 2, INF},

                              {INF, INF, 0, 1},

                              {INF, INF, INF, 0} }

 

Output:

graph[][]=                 { {0, 5, 7 , 8},                                     

                                    {INF, 0, 2, 3},                                                 

                                    {INF, INF, 0, 1},                                            

                                    {INF, INF, INF, 0} }             

Algorithm:

·         n= total number of vertices

·         D(0) = W i.e. the initial weight matrix

·         For k= 1 to n

o   Let D(k)= (dij(k)  ) be a new n x n matrix

o   For i = 1 to n

->  For j = 1 to n

->  min(dij(k-1) , dik(k-1) + dkj(k-1)  ) 

·         return D(n)

C Implementation:

/* Function to implement floydd Warshall Algorithm */

void floydWarshall (intgraph[][V])

{

    int dist[V][V], i, j, k;

/* D(0) = W i.e. the initial weight matrix*/

    for(i = 0; i < V; i++)

        for(j = 0; j < V; j++)

            dist[i][j] = graph[i][j];

 

/* For k= 1 to n

o   Let D(k)= (dij(k)  ) be a new n x n matrix

o   For i = 1 to n

->  For j = 1 to n

->  min(dij(k-1) , dik(k-1) + dkj(k-1)  ) 

*/    

 

for(k = 0; k < V; k++)

    {

        for(i = 0; i < V; i++)

            for(j = 0; j < V; j++)

                if(dist[i][k] + dist[k][j] < dist[i][j])

                    dist[i][j] = dist[i][k] + dist[k][j];

            }

        }

    }

}

 

Time Complexity:

O(V^3)

Constructing The Shortest Path

To construct the shortest pathway a predecessor matrix (P) is required to be calculated at each major cycle (corresponding to k in the above pseudo-code). This method can be implemented in O(|V|3) time

A recursive formulation of the problem can be specified as:

where P is the parent matrix, d is the distance matrix, and W is the weighs matrix.

 

Go to top