The Gateway to Computer Science Excellence
+1 vote
792 views

in Algorithms by Active (1.8k points)
retagged by | 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 .

You get B as answer.

+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

seen none are asking about it .Isnt that important?
+1
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

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
+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.
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
+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.
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)

see this https://gateoverflow.in/171770/algorithm-multistage-graphs

Related questions

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
50,737 questions
57,258 answers
198,086 comments
104,735 users