edited by
6,352 views
25 votes
25 votes

Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph $G$ with $n*n$ adjacency matrix $A$. $A[i,j]$ equals $1$ if there is an edge in $G$ from $i$ to $j$, and $0$ otherwise. Your aim in filling in the blanks is to ensure that the algorithm is correct.

INITIALIZATION: For i = 1 ... n
    {For j = 1 ... n
        { if a[i,j] = 0 then P[i,j] =_______ else P[i,j] =_______;}
    }
    
ALGORITHM: For i = 1 ... n
    {For j = 1 ... n
        {For k = 1 ... n
            {P[__,__] = min{_______,______}; }
        }
    }    
  1. Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
  2. Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
  3. Fill in the blank: The running time of the Algorithm is $O$(___).
edited by

3 Answers

Best answer
21 votes
21 votes
INITIALIZATION: 
For i = 1 ... n {
   For j = 1 ... n { 
      if a[i,j] = 0 then P[i,j] = infinite  
        // i.e. if there is no direct path then put path length as infinite
       else P[i,j] =a[i,j];
   }
}

ALGORITHM: 
For i = 1 ... n { //i loops over the intermediate vertices
   For j = 1 ... n {
      For k = 1 ... n {
               P[j, k] = min( p[j,k] , p[j,i] + p[i,k]);
      }
   }
}              

Time complexity $O(n^3)$

This algorithm is for weighted graph but it will work for unweighted graph too because if $p[i,j]=1$, $p[i,k]=1$ and $p[k,j]=1$  then according to the algorithm $p[i,j] = \min(p[i,j] ,p[i,k] + p[k,j])  = \min(1,2) =1$

And all the other cases are also satisfied. $($like if $p[i,j]$ was $0$ in last iteration and there exist a path via $k)$

selected by
16 votes
16 votes

I'll try to answer in order to provide maximum clarity.

INITIALIZATION: For i = 1 ... n
    {For j = 1 ... n
        { if a[i,j] = 0 then P[i,j] =_______ else P[i,j] =_______;}
    }

We, intialise our final distance matrix initially with the Adjacency matrix of the graph. If we have a path from vertex i to j, then we define it's cost, otherwise we set it to infinite.

so

if a[i,j] = 0 (There is no direct path from vertex i to j)  then P[i,j] =0 else P[i,j]=a[i][j] (Path cost to reach vertex j from i);

Now comes the second part

ALGORITHM: For i = 1 ... n //Consider each vertex to be an intermediate vertex.
    {For j = 1 ... n
        {For k = 1 ... n
            {
          for Each pair of vertices (j,k), find the minimum path to reach k from j and this minimum path has 2 ways
   (1)Either directly go from j to k or
   (2)Using i as an intermediate vertex, go to vertex i from j and then go to k from i.
  Find minimum of above two.
   The ith loop considers for each path, the intermediate vertex that can give minimum cost path to reach k from j.
        P[j,k] = min{P[j][k],p[j][i]+p[i][k]}; }
        }
    }    

Running time of our algorithm is $O(V^3)$ where V is the number of the vertices in the graph.

4 votes
4 votes

It is a Floyd Warshall algorithm(Dynamic Programming approach).

for i = 1 to N     
    for j = 1 to N        
        if there is an edge from i to j          
            dist[0][i][j] = the length of the edge from i to j        
        else           dist[0][i][j] = INFINITY      
for k = 1 to N     
    for i = 1 to N        
        for j = 1 to N           
            dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])
Time Complexity: $O(n^3)$
 
References:
edited by

Related questions

47 votes
47 votes
7 answers
1
Kathleen asked Sep 15, 2014
17,728 views
The running time of the following algorithmProcedure $A(n)$If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$;is best described by$O(n)$$O(\log ...
35 votes
35 votes
2 answers
2
Kathleen asked Sep 15, 2014
11,773 views
The solution to the recurrence equation $T(2^k) = 3T(2^{k-1})+1, T(1) =1$ is$2^k$$\frac{(3^{k+1}-1)}{2}$$3^{\log_2 k}$$2^{\log_3 k}$