NIELIT 2021 Dec Scientist B - Section B: 56

Question

The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ______________.

• A. Total number of vertices 
• B. Total number of edges
• C. Number of vertices $ – 1$
• D. Number of edges $ – 1$

Answer 1

B). Total number of edges ..

 

If the total number of edges in all adjacency list is E , then there will be a total of E number of iterations.  Hence there will be a total of at most E decrease key operations....