193 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

edited | 193 views
0

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 Veteran (74.6k points)
selected by
+1
Hi Bikram Sir ,

Could you pls give an example for A .. the counter example
0
A---1------->B   A is durected to B with edge value 1, B is directed to T with edge value 1,

1/                \1  S  is durected to A with edge value 1 and S is durected to T with edge value 4

S--4--------->T

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.

see the diagram above , this is the counter example that exist.
+1
A connected to B with weight 1, B connected to T weight 1 , S connected to A weight 1 and S connected to T weight 4 , now apply gien condtion , increase edge wegt by 1 for each .. and see P is not shortest path anymore .

D is appropriate as the speciality of bellman ford is that at kth iteration we get k length path weights.. From which minimum can be decided provided vertex is reachable from source.
Hence D) should be correct..
0
@Bikram Sir ,

I am unable to understand the option C . Sir my confusion is that how the no of tree edge can be different ..
each will be having the n-1 edges if graph is having n vertices .
0
0
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.
0
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 ?
+2

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