+1 vote
346 views

retagged | 346 views

B is answer. Go onece for dynamic approch .

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

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

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)

answered by Veteran (23k points) 50 219 362
Apply Dijkstra Algorithm answer  will be B.if u apply hit and trial method u may get correct answer but the approach is wrong
@Pc, can we apply Dijakstra algorithm here?
@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.
answered by Junior (853 points) 1 2 5
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?
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.
answered by Junior (759 points) 12 24
Point to be noted... So in this case what should be the answer???
same doubt why we are applying dynamic approach here?