1 votes 1 votes Algorithms made-easy-test-series algorithms graph-algorithms shortest-path dijkstras-algorithm + – rahul sharma 5 asked Dec 13, 2016 • edited Mar 4, 2019 by akash.dinkar12 rahul sharma 5 1.0k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply dd commented Dec 13, 2016 reply Follow Share please..take the required portion of screen and upload it again :) 0 votes 0 votes rahul sharma 5 commented Dec 13, 2016 reply Follow Share Updated:) 1 votes 1 votes dd commented Dec 13, 2016 reply Follow Share nothing special about it. we have to run Dijkstra on this graph and find out all shortest path costs : add them then minus $7$ 0 votes 0 votes rahul sharma 5 commented Dec 13, 2016 reply Follow Share I did it in similar way.The path from M to S has cost as 7. But the parameter EMax,I have added all the edge wait that were included by dijakstra and i got 22 ,but in the solution they have added each vertex cost instead of edge cost. and they got 58-7 as answer where as i got 22-7 as answer. Am i understansing it incorrect ? 0 votes 0 votes santhoshdevulapally commented Dec 14, 2016 reply Follow Share $E_{max}$ is shortest distance from source vertex to every other vertex in the given graph but not dijkstras graph. 0 votes 0 votes rahul sharma 5 commented Dec 14, 2016 reply Follow Share Lets consider vertex D and S,the shortest distance from M to D is 6 and M to S is 7.Will we add 6+7 to Emax for this,or will we add 1+5+1(Because this is the cost of all edges which shows shortest distance from M to vertex S and D). I hope question is cleared. The question says cost of all edges which shows shortest distance from M to all other vertex ,so we will ad tll the edge cost involved in Dijakstra graph? Please help in understanding this statement 0 votes 0 votes reena_kandari commented Jan 9, 2017 reply Follow Share I also did the same... 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes M-A = 1 M-E1=2 M-D=6 M-A1=3 M-S=7 M-E=8 M-Y=9 M-S1=10 M-C=12 hence the value of emax is sum of all these which is 58. Minimum spaning tree cost is 40 so emax-esp= 58-18 40 Correct me I wrong . Aprajita sachdev answered Jun 3, 2019 Aprajita sachdev comment Share Follow See all 0 reply Please log in or register to add a comment.