search
Log In
18 votes
1.8k views

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$(___).
in Algorithms
edited by
1.8k views
0
here we are not given any information about the weights between the edges, then how can we solve it. The only way I think it can be solved is when A[i,j]= Weight[i,j] if there is an edge in G from i to j.

PLEASE HELP !!!
2

@Bikram

sir need to  edit answer 

P[  j , k ] = min(  p[ j , k ] ,  p[ j , i ] +   p[  i , k ] ) }

3 Answers

17 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 infinite
          else P[i,j] =a[i,j];
         }
    }
ALGORITHM: 
For i = 1 ... n
    {For j = 1 ... n
        {For k = 1 ... n
            {
               P[i, j] = min( p[i,j] , p[i,k] + p[k,j])
            };
        }
    }              

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)$

2 flags:
✌ Edit necessary (mohan123 “P[ j , k ] = min( p[ j , k ] , p[ j , i ] + p[ i , k ] ) }”)
✌ Edit necessary (superak96 “Index variable of the first loop gives intermediate vertex so, the innermost line shoud be P[ j , k ] = min( p[ j , k ] , p[ j , i ] + p[ i , k ] ).”)

edited by
26

ALGORITHM:

For i = 1 ... n

        {For j = 1 ...

                       {For k = 1 ...

                                  { P[  j , k ] = min(  p[ j , k ] ,  p[ j , i ] +   p[  i , k ] ) };

                        }

         }           

1
@prashant , edit the ans
0

@ sid1221

what to edit?

is the last line should change by

P[  j , k ] = min(  p[ j , k ] ,  p[ j , i ] +   p[  i , k ] )

but why we take first point as j ??

0
it has edited ,.. now correct ..
0
The comment by himanshu is the standard way of implementing the all pairs shortest path.First loop gives intermediate vertex.

Although given answer also seems correct
6
It's wrong. This will give incorrect answers. @Himanshu1 is correct.
1

@Rishabh Gupta 2  Sir

Could you please explain why the above one  is wrong. In the Cormen book ,

p[i,j]=min{p[i,j],p[i,k]+p[k,j]} is given.

0
why are diagonal elements not initialized to zeroes?
0
what is wrong in that? It is same as in cormen
0

@Arjun Sir

Plz tell me which code is correct here. I am not getting, what is wrong in answer.

0

yes @Himanshu1 is correct here. First create an edge with inner most two loops and then checking an external point with outer most loop. discuss

8 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.

0

@Ayush Upadhyaya

As it is given 0 or 1 we donot consider the edge weights here so finally it boils down to a boolean  variable having 0 or 1

so  can this

P[j,k] = min{P[j][k],p[j][i]+p[i][k];

be not written as:

P[j,k] = min{P[j][k],p[j][i] & p[i][k]);

&=logical 'and'.

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

31 votes
6 answers
1
5.4k views
The running time of the following algorithm Procedure $A(n)$ If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$; is best described by $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$
asked Sep 16, 2014 in Algorithms Kathleen 5.4k views
26 votes
2 answers
2
4.2k 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}$
asked Sep 15, 2014 in Algorithms Kathleen 4.2k views
63 votes
3 answers
3
9k views
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree ... described by which of the following? $\log_2 n$ $\log_{\frac{4}{3}} n$ $\log_3 n$ $\log_{\frac{3}{2}} n$
asked Sep 16, 2014 in DS Kathleen 9k views
16 votes
3 answers
4
1.3k views
Minimum sum of product expression for $f(w,x,y,z)$ shown in Karnaugh-map below $xz + y'z$ $xz' + zx'$ $x'y + zx'$ None of the above
asked Sep 15, 2014 in Digital Logic Kathleen 1.3k views
...