1 votes 1 votes Algorithms algorithms graph-algorithms shortest-path test-series + – Rakesh K asked Nov 27, 2016 • retagged Jul 17, 2022 by makhdoom ghaya Rakesh K 3.2k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Rakesh K commented Nov 27, 2016 reply Follow Share A and B seems to be having smae cost, so is one preferable to another? 0 votes 0 votes utk0203 commented Dec 24, 2016 reply Follow Share BUT WHAT IS THE EDGE WEIGHT OF EDGE 5-8 seen none are asking about it .Isnt that important? 3 votes 3 votes utk0203 commented Dec 24, 2016 reply Follow Share Bt removing edge 5-8 and applying D.A. 1-2-4-8-9 cost=15 1 votes 1 votes Please log in or register to add a comment.
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. Bongbirdie answered Jun 6, 2017 Bongbirdie comment Share Follow See all 3 Comments See all 3 3 Comments reply Er Udit Mishra commented Aug 13, 2017 reply Follow Share Point to be noted... So in this case what should be the answer??? 0 votes 0 votes set2018 commented Oct 7, 2017 reply Follow Share same doubt why we are applying dynamic approach here? 0 votes 0 votes Lakshman Bhaiya commented Jun 19, 2018 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.
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 https://gateoverflow.in/35239/final-analysis-dijikstra-algorithm pC answered Nov 27, 2016 pC comment Share Follow See all 3 Comments See all 3 3 Comments reply sethi commented Dec 23, 2016 reply Follow Share 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 votes 0 votes rahul sharma 5 commented Sep 28, 2017 reply Follow Share @Pc, can we apply Dijakstra algorithm here? 0 votes 0 votes pC commented Sep 28, 2017 reply Follow Share @rahul_sharma_5 , read that ref (final analysis ) , it will make more clarity 0 votes 0 votes Please log in or register to add a comment.
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. shayal chhabra answered Dec 14, 2016 shayal chhabra comment Share Follow See all 3 Comments See all 3 3 Comments reply Bongbirdie commented Mar 13, 2017 reply Follow Share 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? 2 votes 2 votes aditi19 commented Jul 6, 2018 reply Follow Share I too got the same result. Yes it's correct 0 votes 0 votes Snape commented May 6, 2021 reply Follow Share My answer is also 14 0 votes 0 votes Please log in or register to add a comment.