edited by
1,458 views
3 votes
3 votes

State the TRUE one among these choices:

  1. Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t . 
  2. Dynamic programming is more closely related to BFS than it is to DFS.
  3. A depth-first search of a directed graph always produces the same number of tree edges (i.e. independent of the order in which the vertices are provided and independent of the order of the adjacency lists). 
  4. If a weighted directed graph G is known to have no shortest paths longer than k edges, then it suffices to run Bellman-Ford for only k passes in order to solve the single-source shortest paths problem on G.
  1.  a
  2.  b
  3.  c
  4.  d
edited by

1 Answer

Best answer
2 votes
2 votes
D option is true ,

The ith iteration finds shortest paths in G of i or fewer edges, by the path relaxation property (see p. 587 in CLRS) .

A is false , just draw a directed connected graph and see counter example exist.

B is false bacause DFS is more closely related. The top-down approach to dynamic programming is effectively performing DFS on the subproblem dependence graph. The bottom-up approach means solving subproblems in the order of a reverse topological sort, which is also related to DFS.

C is false because The DFS forest may contain different numbers of trees (and tree edges) depending on the starting vertex and upon the order in which vertices are searched .
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
1,640 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
1 votes
1 votes
3 answers
3
0 votes
0 votes
0 answers
4