Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G…

GATE · 2003 · CS

Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ......., vj) such that (vk, vk+1) ∈ 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 x 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, j] ≥ n - 1, then G has a Hamiltonian cycle
C.
If there exists a path from j to k, A[j, k] contains the longest path length from j to k
D.
If there exists a path from j to k, every simple path from j to k contains at most A[j, k] edges

Attempted by 145 students.

Explore the full course: Gate Guidance By Sanchit Sir