1,032 views

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

### 1 comment

Sir as it was given that the shortest path contain no more than K edges that's why it take K iteration ..otherwise it will K+1 (to check for cycle in (K+1) th iteration)..??

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 .
by

tree edges may be different as it depends on dfs traversal means the traversal itself and one can have multiple dfs traversal possible in a single graph. Also from which vertex you start your depth-first search is also matters ( the starting vertex).

considering these 2 points C is false.
Yes Sir , I m fine with that the a graph can have multiple DFS traversal depending on the starting vertex . But i m confused about the no of tree edges ? yeah the order of tree edges can be different as well as tree edges can also be differenet but what about no of tree edges?

As traversal will be tree so n-1 edges will be there in each case ?

No it is not n-1, depends on which node is start node

Consider the following graph. If we start from 'a', then there is one tree edge. If we start from 'b', then there is no tree edge.

a---->b  it is directed and direction is from a to b though u may start with b is not it ?

http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2008-sol.pdf