All pair shortest paths - Repeated Squaring.

Given a matrix which represents 1/0 representing a direct flight between two places in a 2D array, find the number of hops required to reach from one place to another place. In other words, find if it is bi-hop, tri-hop etc.


Approach: 

A dynamic-programming algorithm.

Assume input graph is given by an adjacency matrix.

W = (wij)

Let dij(m)  = minimum weight of any path from vertex i to vertex j,

                  containing at most m edges.

dij(0) =   0   if i = j

         =     (infinite)  if i != j

dij(m) = min(dij(m-1), min{dik(m-1) + wkj})

        = min1 <= k <= n{dik(m-1) + wkj}, since wjj = 0.

So, given W, we can simply compute a series of matrices D(1), D(2), …,

D(n-1) where:

D(1) = W

D(m) = (dij(m))

SP algorithm computes the

following matrix “products”:

D(1) = D(0)*W = W1

D(2) = D(1)*W = W2

D(3) = D(2)*W = W3

...

D(n-1) = D(n-2)*W = Wn-1

n := rows[W];

D(1) := W;

m := 1;

while n – 1 > m do

D(2m) := Extend-SP(D(m), D(m));

       m := 2m

od;

return D(m) 

Extend-SP(D, W)

n := rows[D];

for i := 1 to n do

for j :=1 to n do

d´ij := ;

for k := 1 to n do

d´ij := min(d´ij, dik + wkj)

od

od

od;

return D´  

Code: