Floyd Warshall Algorithm

The problem is to find shortest distances between every pair of vertices in a given edge weighted directed graph.

The graph is represented in the form of an adjacency matrix where each cell A[i][j] represents the weight of the edge from vertex i to vertex j.
If i==j,then A[i][j]=0.
If there is no edge from vertex i to vertex j,then A[i][j]=INF.

Algorithm-

We update the matrix by considering all the vertices as intermediate vertex one by one.
If vertex number k is selected,for every pair(i,j),there are two possible cases.
1. k is not an intermediate vertex.Thus,dist[i][j] remains the same.
2. k is an intermediate vertex.Thus,dist[i][j]=dist[i][k]+dist[k][j].

dist[i][j]= min (dist[i][j],dist[i][k]+dist[k][j]) for k=0,1.....N-1.

Its time complexity is O(N^3).

Code-

//N is the number of vertices.
//dist[][] denotes the adjacency matrix.
for(k=0;k<N;k++) //choosing an intermediate vertex
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
dist[i][j]=std::min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
//Updated dist[][] contains shortest distance
// between each pair of vertices.

Note-

1. INF can be taken as INT_MAX from in C.
2. This algorithm can also be used to find the transitive closure which means the minimal pairs that convert a set S into a transitive set.A set S is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c.
Example of a transitive set- { (2,3),(3,4),(2,4) }

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

42,383 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>