Fill-in-the-Blanks
Question 1 |
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 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{_______,_______};}
}
}
- (a) Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
(b) Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
(c) Fill in the blank: The running time of the Algorithm is O(____).
Theory Explanation is given below. |
Question 1 Explanation:
(a) INITIALIZATION: For i = 1 ... n
{ for j = 1 ... n
{ if a[i,j] = 0 then P[i,j] = infinite;
else P[i,j] = a[i,j];
}
}
(b) 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])
}
}
}
(c) Actual graph:
MST: There are 2 possible MST's
{ for j = 1 ... n
{ if a[i,j] = 0 then P[i,j] = infinite;
else P[i,j] = a[i,j];
}
}
(b) 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])
}
}
}
(c) Actual graph:
MST: There are 2 possible MST's
There is 1 question to complete.