0 votes 0 votes Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify.. Algorithms algorithms graph-algorithms + – Shamim Ahmed asked Nov 25, 2018 Shamim Ahmed 540 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply gauravkc commented Nov 25, 2018 reply Follow Share Maximum number of short edges?. The statement is ambiguous or I'm not getting it. Can you explain the statement? 0 votes 0 votes Shamim Ahmed commented Nov 25, 2018 reply Follow Share Please refer this question:- https://gateoverflow.in/1765/gate2012-40 0 votes 0 votes Swapnil Naik commented Nov 25, 2018 reply Follow Share From my point of view: The statement says dijktra select nodes for shortest path such that they should have maximum number of shortest edges and node are non-adjacent. From below diagram node 2, 3, 6 are non adjacent and have maximum no. of shortest edges but they are not included in the shortest path, hence I think given statement is false. or it could have another meaning, it selects the shortest path as maximum no. of shortest edges, so that path will be 0-1-2-6-4 as it is one of the path having maximum no. of shortest edges, but you can see in result shortest path is different hence again I can say given statement is false. 0 votes 0 votes gauravkc commented Nov 25, 2018 reply Follow Share I feel it is not always the case. In this example, path should be 1-3-4-5-6 but it prints 1-2-7-6 0 votes 0 votes Shamim Ahmed commented Nov 25, 2018 reply Follow Share So the statement is essentially not true. Can we conclude.. we must access such questions based on the options given. Because even if we use algorithm to find shortest path... there are many possibilities. 0 votes 0 votes gauravkc commented Nov 25, 2018 reply Follow Share Yup. When there are choices, result depends upon how algorithm is executing each step. It's better to execute algorithm. 0 votes 0 votes Please log in or register to add a comment.