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

asked in Algorithms by Active (1.7k points)  
retagged by | 278 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

3 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 (21.1k 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 (811 points)  
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?
+1 vote
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 (587 points)  
Point to be noted... So in this case what should be the answer???


Top Users Aug 2017
  1. ABKUNDAN

    4654 Points

  2. Bikram

    4032 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2856 Points

  5. manu00x

    2664 Points

  6. makhdoom ghaya

    2380 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1756 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,878 questions
31,952 answers
74,104 comments
30,065 users