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].
[cpp]dist[i][j]= min (dist[i][j],dist[i][k]+dist[k][j]) for k=0,1…..N-1.[/cpp]
Its time complexity is O(N^3).
Code-
[cpp]
//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.
[/cpp]
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) }
