The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
884 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$(___).
asked in Algorithms by Veteran (59.5k points)
edited by | 884 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 Answers

+12 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 as if $p[i,j]$ was $0$ in last iteration $nd$ there exist a path via $k$)

answered by Active (2.2k points)
edited by
+7

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
+1
It's wrong. This will give incorrect answers. @Himanshu1 is correct.
+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:
answered by Active (4.7k points)
edited by

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,111 questions
44,694 answers
127,232 comments
43,753 users