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

**of the edge from vertex i to vertex j.**

*weight*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) }