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