+1 vote
792 views

retagged | 792 views
+2

B is answer. Go onece for dynamic approch .

Short cut Go with End vertex to start vertex with minmum cost every time .

+1
or try all options
0
A and B seems to be having smae cost, so is one preferable to another?
+3
BUT WHAT IS THE EDGE WEIGHT OF EDGE 5-8

+1
Bt removing edge 5-8

and applying D.A.

1-2-4-8-9

cost=15

Option B

Multi stage graph if we follow greedy strategy answer will not always be optimum . Dynamic Approch is prefered here .

Like @anirudh said  for short-cut

Start  with End vertex and traverse to  start vertex with minmum cost every time

For General Approch . Watch this (https://www.youtube.com/watch?v=m5Y-4TsXsJ0)

by Boss (21.5k points)
0
Apply Dijkstra Algorithm answer  will be B.if u apply hit and trial method u may get correct answer but the approach is wrong
0
@Pc, can we apply Dijakstra algorithm here?
0
@rahul_sharma_5 , read that ref (final analysis ) , it will make more clarity
In this A and B both are havinng same cost, but if we follow greedy approach it will not give A as answer as till it ll not get less cost it will use previous only and from dynamic both answers are correct so B should be the answer.

In multistage we start from end vertex not from starting vertex if we start from starting vertex then A should be the answer but according to  multistage algo B should be the answer.
by Junior (875 points)
+2
When I am calculating, the answer is turning out to be

1-->2-->4-->8-->9

Sum= 14

Shouldn't this be the accurate answer?
0
I too got the same result. Yes it's correct
This is not a multi-stage graph since, in a multistage graph, edges can only be present between stage i and stage (i+1). Here, we have an edge from 1 to 5 i.e. stage 1 to stage 3 which is not correct.
by Junior (705 points)
0
Point to be noted... So in this case what should be the answer???
0
same doubt why we are applying dynamic approach here?
0

Because Dijkstra Algorithm takes O(E log V )time.

And Using Dynamic Programming time complexity = O($V^{2}$) = O(E)