# Graph Algorithms

98 views
Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..
0
Maximum number of short edges?. The statement is ambiguous or I'm not getting it. Can you explain the statement?
0

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.

## Related questions

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)