The Gateway to Computer Science Excellence
0 votes
56 views
Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..
in Algorithms by Active (2.4k points) | 56 views
0
Maximum number of short edges?. The statement is ambiguous or I'm not getting it. Can you explain the statement?
0

Please refer this question:- https://gateoverflow.in/1765/gate2012-40

0

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

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
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
Yup. When there are choices, result depends upon how algorithm is executing each step. It's better to execute algorithm.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,578 answers
195,771 comments
101,769 users