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.


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).


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


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 *

41,055 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>