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.

The Gateway to Computer Science Excellence

+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

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.

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.

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,258 answers

198,086 comments

104,735 users