edited by
585 views
0 votes
0 votes

Let $G (V, E)$ be a directed graph with $n$ vertices.

A path from $v_i$ to $v_j$ in $G$ is sequence of vertices $(v_i, v_{i+1}, \ldots, 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 follow:
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?

(A) $A[j, k] = n$
(B) If $A[j, k] = n – 1$, then $G$ has a Hamiltonian cycle
(C) If there exists a path from $j$ to $k$, then $A[j, k]$ contains the longest path length from $j$ to $k$
(D) If there exists a path from $j$ to $k$, then every simple path from $j$ to $k$ contain most $A[j, k]$ edges.

I am confused between option C and D , answer given is D .

edited by

1 Answer

1 votes
1 votes
I traced it with 4 vertex .. i didnt get logest path  after terminate the algo... but option d follow ...  option c may  be changed by changing in no of vertex ...

aur one more thing  if directed graph has loop then option c always wrong bcoz longest path will be tends to infinite

Related questions

0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
gate_forum asked Dec 25, 2015
1,076 views
minimum running time of algo that determines universal sink in a directed graph G={V,E} - a vertex with indegree |V|-1 and outdegree 0, given an adjacency matrix for G is...