Explain all pair shortage path with algorithm and example

Let G be the directed graph with edges and vertices G (V, E ). Basically the all pair shortage path problem determines the matrix A such that A [ i, j ] be the length of the shortage path from i to j. Since each application from this procedure requires O( n² ) time. In this problem, we only have required a graph with no cycle and negative length. If we allow a graph to contain a cycle and negative value then the shortage path between the two vertices may have -∞ length. Following is the algorithm, that may useful to find out the all pair shortage path.

Algorithm AllPair ( cost, A, n)

{

// A [i, j] is the cost of shortage path from i to j

for i = 0 to 1 do

for j = 0 to 1 do

A [ i, j ] = cost [i, j ];

for i=0 to 1 do

for j=0 to 1 do

A [i,j ] = min [ A( i, j ), A( i, k ), A(k, j ) ]  

}

  

For example consider the directed graph. Associated cost matrix of above digraph is as follows

 

For finding the all pair shortage path for matrices we must have concentrate on following

A [i, j] = min { min { A^k-1 (i, k) + A^k-1 (k, j) } , cost (i, j) }

As its 3 *3 matrix, lets consider first k=1, so the above equation will be solve as follows :

A¹ ( 3,2 ) = min { min { A^1-1 (3,1) +  A^1-1 (1,2) }, cost (3,2)

= min {min (3 + 4), ∞}

= 7

A² ( 1,3 ) = min {min { A^2-1 (1,2) + A^2-1 (2,3) }, cost ( 1,3 )

= min {min (4 + 2), cost 11}

= 6

A³ ( 2,1 ) = min {min { A^3-1 (2,3) + A^3-1 (3,1) }, cost ( 2,1 )

= min {min (2 + 3), 6}

= 5

So the matrix is updated as follows