Ace Test Series: Algorithms - Graph Algorithms

Question

(A). When a recurrence relation has a cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.

(B). Given a connected graph $G(V,E)$ if a vertex $v$ $\epsilon$ $V$ is visited during level $K$ of a breadth first search from source vertex $s$ \epsilon $V$, then every path from $s$ to $v$ has length at most $k$ 

(C). Every sorting Network with $n$ inputs has depth \omega(n)

(D). Both (A) & (B)

Which of the following statement is TRUE?

Argument: I dont have much idea about A, but it seems to be true. For B, with BFS tree we get the shortest path possible from source vertex. So, every other possible path should have the length of atleast 'k'. Given wording is 'atmost'. So, B should be wrong.

Given answer is D.

Comments

B is right since if any vertex is at a distance of k from source vertex then u cannot get a shortest distance of more than k using BFS  , correct word is atmost.

Answer 1

Use Breadth first search to mark label the distances of all the nodes within k hops of the source vertex.

Now, if the destination can be reached within k hops, run Dijkstra's algorithm to find the shortest path, using all the labelled nodes, to the destination vertex. therefore modified  bfs can be used to find length of shortest path from source vertex to  destination vertex  for atmost k length. correct if i am wrong therfore b option is wrong na