First time here? Checkout the FAQ!
0 votes

asked in Algorithms by Active (1.6k points)  
retagged by | 226 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?

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

and applying D.A.



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 (


Good Read

answered by Veteran (20.7k 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


Sum= 14

Shouldn't this be the accurate answer?
0 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 (557 points)  

Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Arnab Bhadra

    1502 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1481 Points

  5. junaid ahmad

    1432 Points

  6. Debashish Deka

    1384 Points

  7. Rupendra Choudhary

    1220 Points

  8. rahul sharma 5

    1220 Points

  9. Arjun

    1168 Points

  10. srestha

    1010 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. Arjun

    208 Points

  2. akankshadewangan24

    152 Points

  3. Debashish Deka

    138 Points

  4. Hira Thakur

    130 Points

  5. Soumya29

    106 Points

23,399 questions
30,111 answers
28,426 users