2.2k 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
edited | 2.2k views
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.
@rahul, it is not all pairs shortest path floyed warshall algo.we are using "max" here.this is something else!!

D is correct.

Consider a graph with $2$ nodes and one edge from to $V_1$ and $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

edited by
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..

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

....

For the first case , i m geting matrix as -

2        3

3        4

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 ????

a[1][2] + a[2][1] = 1 + 0, thats how
why not option c?
it is taking complete graph. right?
Why confusion?
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??

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

@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

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??

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

why do u think it shouldnt have?
Question mentions that path exists from Vi,Vi+1 so V1,V2  is ok but V2 to V1??
@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......
I tried but cannot rule out option A  unless an edge of the type v2 to v1 is involved.
@gupta

post your working....may be i can help :)

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)

@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

@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?

@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

@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

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.

@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 :)

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.
I have drawn that graph but can you please explain option C and D? I don't understand it.