3.9k 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 | 3.9k 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.
+6
@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.
+1
$A path from vi to vj in G is a sequence of vertices (vi,vi+1,…,vj) such that (vk,vk+1)∈E for all k in i through j−1.$

can someone clear the meaning of this line?

can we move only in increasing number of vertices?.

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

$$\begin{array}{|l|l|l|} \hline \textbf{A} & \textbf{1} & \textbf{2} \\\hline \textbf{1} & \text{1} & \text{2} \\\hline \textbf{2} & \text{1} & \text{2} \\\hline \end{array}$$

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
$$\begin{array}{|l|l|l|} \hline \textbf{A} & \textbf{1} & \textbf{2} \\\hline \textbf{1} & \text{2} & \text{3} \\\hline \textbf{2} & \text{3} & \text{4} \\\hline \end{array}$$

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

D is correct

edited
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 :)
0

But this algorithm behaves differently on this graph

it's matrix A[i][j] intially is

$\begin{pmatrix} 0 &1 &0 &0 \\ 0 &0 & 0 &1 \\ 0& 1& 0 &1 \\ 0& 0 &0 & 0 \end{pmatrix}$

And after executing this program I get A[i][j] as below

$\begin{pmatrix} 25 &26 &28 &44 \\ 25 &26 & 28 &44 \\ 28& 29& 31 &47 \\ 43& 44 &46 & 62 \end{pmatrix}$

program code and results : https://ideone.com/q13cqi

I find none of the option correct here :(

0
how 25??  :O

Can u dry run ur code?
0

Actually

every simple path from j to k contains at most A[j,k] edges

That means this simple path is the longest path of the graph

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)

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

An example to support answer D.

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

1
2