GATE CSE
First time here? Checkout the FAQ!
x
0 votes
151 views

asked in Algorithms by Active (1.6k points)  
retagged by | 151 views

B is answer. Go onece for dynamic approch . 

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

You get B as answer.

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

seen none are asking about it .Isnt that important?
Bt removing edge 5-8

and applying D.A.

1-2-4-8-9

cost=15

2 Answers

+2 votes

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)

 

Good Read

answered by Veteran (20.2k points)  
Apply Dijkstra Algorithm answer  will be B.if u apply hit and trial method u may get correct answer but the approach is wrong
+2 votes
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 (689 points)  
Top Users Feb 2017
  1. Arjun

    5288 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1690 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,860 questions
26,010 answers
59,673 comments
22,113 users