Find shortest path

Question

Consider the multistage graph with $\mathrm{K}=5$ then find out minimum cost from S to T ?

• A. $1 \rightarrow 3 \rightarrow 6 \rightarrow 8 \rightarrow 9$
  
• B. $1 \rightarrow 2 \rightarrow 6 \rightarrow 8 \rightarrow 9$
  
• C. $1 \rightarrow 5 \rightarrow 7 \rightarrow 9$
  
• D. $1 \rightarrow 2 \rightarrow 6 \rightarrow 7 \rightarrow 9$

Comments

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

---

Backward DP gives us 1-2-4-8-9 which 4+3+3+4 = 14 not 15

Answer 1

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.

Comments

Point to be noted... So in this case what should be the answer???

---

same doubt why we are applying dynamic approach here?

---

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

Answer 2

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

• https://gateoverflow.in/35239/final-analysis-dijikstra-algorithm

Comments

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

Answer 3

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.

Comments

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?

---

I too got the same result. Yes it's correct

---

My answer is also 14