The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.7k views

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_k+1) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex appears more than once.

Let $A$ be an $n \times n$ array initialized as follows:

$$A[j,k] = \begin{cases} 1 \text {,   if } (j,k) \in E \\ 0 \text{,   otherwise} \end{cases}$$

Consider the following algorithm:

for i=1 to n
    for j=1 to n
        for k=1 to n
            A[j,k] = max(A[j,k], A[j,i] + A[i,k]);  

Which of the following statements is necessarily true for all $j$ and $k$ after termination of the above algorithm?

  1. $A[j,k] \leq n$
  2. If $A[j,j] \geq n-1$ then $G$ has a Hamiltonian cycle
  3. If there exists a path from $j$ to $k$, $A[j,k]$ contains  the longest path length from $j$ to $k$
  4. If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
asked in Algorithms by Veteran (59.5k points)
edited by | 2.7k views
0
Its Floyd wars hall algorithm with edge weights as 0 or 1.

At the end of this we will have all paris shortest path.A[i][j] will tell shortest path from i to j. If A[i][j]=x then it means shortest path has cost as x.As it is a binary weight graph ,then x means x number of edges from i to j.

So d is correct.
0
@rahul, it is not all pairs shortest path floyed warshall algo.we are using "max" here.this is something else!!
0
Anyone have another simpler explanation. Do, kindly share.

4 Answers

+27 votes
Best answer

D is correct.

Consider a graph with $2$ nodes and one edge from $V_1$ to $V_2$,

Running the above algorithm will result in A being 

A 1 2
1 1 2
2 1 2

Clearly options B and C are wrong. Since

  1. $A[1][1]$ and $A[2][2] > n-1$ and there exists no Hamiltonian cycle. Hence invalid.
  2. The longest path between $V_1$ and $V_2$ is $1$, but $A[1][2]$ is $2$, which is invalid. And no path between  $V_2$ and $V_1$ yet $A[2][1] = 1$ // it should be max cost path between j and k, not path length.

Hence A or D could be valid.

Now consider a graph with $2$ nodes and two edges, one from  $V_1$ and $V_2$ and other form $V_2$ and $V_1$. Running the above algorithm will result in A being

A 1 2
1 2 3
2 3 4

Hence option A is invalid, as $A[i][j]$ can be $>n$

D is correct

answered by Active (3.5k points)
edited by
0
sorry i cant understand . (assume first case, one edge from v1 to v2) condition says, a[1,2] = 1,a[1,1] = 0,a[2,2] = 0. now in program a[1,1] should be = "a[1][1] = max(a[1][1],a[1]+a[1])" which is 0 right ??

 

plz help..
0

a is a 2d array, and you cannot assign a[1] directly to an integer.

for k = 1

    a[1][1] = max(a[1][1],a[1][1]+a[1][1])

    a[1][2] = max(a[1][2],a[1][1]+a[1][2])

    a[2][1] = max(a[2][1],a[2][1]+a[1][1])

    a[2][2] = max(a[2][2],a[2][1]+a[1][2])

    ....

Does this answer your question ?

+2

For the first case , i m geting matrix as -

2        3

3        4

0

ya .thats what.

 a[1][1] = max(a[1][1],a[1][1]+a[1][1]) . so a[1][1] = O right ??? . since we have only an edge between v1 to v2 ?? thats what i cannot understand how a[1][1] = 1 ???? 

0
a[1][2] + a[2][1] = 1 + 0, thats how
0
why not option c?
0
Please read the explanation, i have explained it there.
0
it is taking complete graph. right?
0
Why confusion?
0
why have u considered cost from v2 to v1 as 1 in the original graph?? Its mentioned in the question itself tat vi->vi+1= 1 and rest all 0??
+1

@ryan sequeira 

$$A[j,k] = \begin{cases} 1 \text { if } (j,k) \in E \\ 0 \text{ otherwise} \end{cases}$$
Here if A[j,k] is the number of edges from j to k (i.e. path length from j to k), then answer would be C, right ?

0
@ryan

how are u filling the values in table

A[1,1] = max ( A[1,1]  , 0)

A[1,1] = 0 because no path from vertex V1 to V1

therefore shouldnt it be 0?

C and D are correct i suppose
0

It is mentioned in the answer 

 it should be max cost path between j and k not path length.

I think it does not even give correct result for maximum cost path.As in first example ,1->2 path is 2 in the result but actually it is 1.Please check??

0
i am having the same doubt as  @sushmita Veteran. Can anyone clarify how the edge from v2 -> v1 is permissible??
0
@gupta

why do u think it shouldnt have?
0
Question mentions that path exists from Vi,Vi+1 so V1,V2  is ok but V2 to V1??
0
@gupta

yes that seems to be a valid point

so you  could try an example using this to rule out the options and find the correct one......
0
I tried but cannot rule out option A  unless an edge of the type v2 to v1 is involved.
0
@gupta

post your working....may be i can help :)
+6 votes

G=(V,E) has n vertices.

(Vi,Vj) can have a path more than 1 edges

if that is the case we will take maximum length path

A[j,k] = max(A[j,k], A[j,i] + A[i,k]);

Now take an example with 2 vertices

  1 2
1 0 1
2 0 0

Here we can check option B) A[1,1]=0<(n-1)=2-1=1

So, this option false

Now, take another graph where loop is present

In option C)says A[j,k] contains  the longest path length from to k

But if there is a loop present then longest path will contain the loop.

See here A[1,1]=1->2->1

But according to algorithm we can work with only simple path

So, this option also false.

Now, A) option

See, A[1,2] max length of path is 3, as 1 contain a self loop.

A[1,2]=3>2=n [where n is number of vertices

Atlast option D) If there exists a path from to k, every simple path from to k contains at most A[j,k] edges

it is completely TRUE. As it is clearly mention simple path.

So, Ans D)

answered by Veteran (91.7k points)
0

@srestha

Here we can check option B) A[1,1]=0<(n-1)=2-1=1

So, this option false

By this statement we cannot make B as false

Option B says - 

  1. If A[j,j]≥n−1 then G has a Hamiltonian cycle

To prove its wrong

A[1,2] = 1 which is >= (n-1)          [ n-1 = 2-1 = 1]

and still it doesnt have hamiltonian cycle

so its false

0

@aish
yes, you have a valid point. we can't prove option B false like that. But
A[1,2] is A[i,j]
option B is A[j,j]
both indexes should be same.
 

@srestha 
I don't think it is given that we have to take only simple paths, as that a just an isolated statement given in the question. So how now option C is false?


I didn't get How did you prove Option A wrong, A[2,1]=3? As you consider we can take only a Simple path, so we can't consider loop on A, is it not so?

0

@bhuv

yea sorry

so  

  1. If A[j,j]≥n−1 then G has a Hamiltonian cycle

Consider the graph with the self loop

now A[1,1] = max ( A[1,1] , A[1,2] + A[2,1] )

This will surely have some value which is greater than n-1 but still it doesnt form a hamiltonian cycle

therefore false

0

@bhuv

OPTION C

If there exists a path from j to kA[j,k] contains  the longest path length from j to k

Consider the self loop graph

A[1,2] = max (A[1,2] , A[1,i] + A[i,k] )

there is no node to be taken as i...since only 2 nodes are available

therefore A[1,2] will be 1

so the path from A[1,2] is 1 but that isnt the longest path between j and k

therefore false

OPTION A

A[j,k]≤n

as proved for OPTION B.....A[1,1] can have a very large value due to the self loop and will definetely be greater than 

therefore false

0

OPTION C

If there exists a path from j to kA[j,k] contains  the longest path length from j to k

Consider the self loop graph

A[1,2] = max (A[1,2] , A[1,i] + A[i,k] )

there is no node to be taken as i...since only 2 nodes are available

therefore A[1,2] will be 1

so the path from A[1,2] is 1 but that isnt the longest path between j and k

therefore false

I'm inferring from this that
A[1,2] = max (A[1,2] , A[1,1] + A[1,2] )
A[1,2] = max (A[1,2] , A[1,2] + A[2,2] )

are the possible values of i from outer loop which are possible (I think) and due to self-loop at vertex V1 A[1,1] can get significantly large values but still can't taken for valid "longest path" for A[1,2] as more is possible.

Also, I'm able to infer that the statement regarding "Simple path" in question doesn't play any role because the examples we are using contains non-simple paths. 

Please suggest if I'm understanding something incorrectly.

0

@bhuv

A[1,2] = max (A[1,2] , A[1,1] + A[1,2] ) 

Here u have taken A[1,1] + A[1,2] which is A[j,j] + A[j,k] and not  A[j,i] + A[i,k] which is asked in the question

therefore it never considers the self loop at all

and therefore gives only simple paths

This is my understanding :)

+3 votes
Solution:D

Tracing this algorithm on a simple graph with two nodes(with only one edge form node 1 to node 2) revels that the only statement that can be true about this algorith is D.
answered by Active (1.4k points)
0
I have drawn that graph but can you please explain option C and D? I don't understand it.
+2 votes

 

An example to support answer D.

 

answered by (179 points)


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

38,058 questions
45,554 answers
131,887 comments
48,909 users