search
Log In
0 votes
98 views
Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..
in Algorithms 98 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

0 votes
2 answers
1
396 views
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS (Depth First Search) tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)
asked Jan 4, 2019 in Algorithms Abhishek Kumar 38 396 views
0 votes
0 answers
2
117 views
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ?
asked Jan 2, 2019 in Algorithms Prince Sindhiya 117 views
0 votes
0 answers
3
101 views
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!! like 11-12-12 then for second square 4 times 13 so c(4,2) any two of then lead to me @ answer @6.
asked Dec 26, 2018 in Algorithms CHïntän ÞäTël 101 views
0 votes
0 answers
4
...