Official PYQ · 2003Q70Graph Traversals (BFS, DFS)MCQ1 mark

GATE CS 2003 Q70 — Graph Traversals (BFS, DFS)

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?

View worked solution

Answer: D

The given algorithm is a variation of the Floyd-Warshall algorithm, where the min operation is replaced by max. Since all initial edge weights are $1$ , any update of the form $A[j,k] = \max(A[j,k], A[j,i] + A[i,k])$ computes the length of some walk from $j$ to $k$ .

Let $P = (v_0, v_1, \dots, v_m)$ be any simple path from $j = v_0$ to $k = v_m$ of length $m$ . Since $P$ is a simple path, all its vertices are distinct. We can show by induction on the maximum index of the intermediate vertices that the algorithm will eventually find a walk of length at least $m$ :

Let $i$ be the vertex in the intermediate set of $P$ with the largest index.
The subpaths from $j$ to $i$ and from $i$ to $k$ only use intermediate vertices with indices strictly smaller than $i$ .
By induction, before the outer loop reaches step $i$ , we have $A[j,i] \ge \text{length}(j \to i)$ and $A[i,k] \ge \text{length}(i \to k)$ .
At step $i$ , the algorithm updates $A[j,k] = \max(A[j,k], A[j,i] + A[i,k])$ , ensuring $A[j,k] \ge \text{length}(P) = m$ .

Since $A[j,k]$ only increases in subsequent steps, the final value of $A[j,k]$ is at least the length of any simple path from $j$ to $k$ . Thus, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Graph Traversals (BFS, DFS) questions

GATE CS 2003 Q70 — Graph Traversals (BFS, DFS)

Related questions