retagged by
3,086 views
1 votes
1 votes

retagged by

3 Answers

3 votes
3 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.
2 votes
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

2 votes
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.

Related questions

5 votes
5 votes
2 answers
1
jenny101 asked Oct 26, 2016
1,168 views
1 votes
1 votes
1 answer
2
jenny101 asked Oct 26, 2016
562 views
1 votes
1 votes
3 answers
3
3 votes
3 votes
2 answers
4
dd asked Dec 6, 2016
2,594 views
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a sho...