GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
346 views

asked in Algorithms by Active (1.9k points) 2 28 50
retagged by | 346 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 (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
+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 (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?
+2 votes
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?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23706 Points

  2. Bikram

    17298 Points

  3. Habibkhan

    9336 Points

  4. srestha

    6566 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5188 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4514 Points

  9. manu00x

    4158 Points

  10. sushmita

    4098 Points


Recent Badges

Verified Human Terminator
Verified Human maheshtheng
Nice Answer Ahwan
Renewal Ahwan
Notable Question pranab ray
Notable Question Tuhin Dutta
Great Question jothee
Ancestor santhoshdevulapally
Nice Question Pradip Nichite
Famous Question smartmeet
27,447 questions
35,307 answers
84,718 comments
33,549 users