Given pseudo code of Dijkstra's Algorithm.
//Initialise single source(G,s)
S=0
Q=V[G]
While Q != 0
Do u=extract-min(Q)
S=S union {u}
For each vertex v in adj[u]
Do relax(u,v,w)
What happens when "While Q != 0" is changed to "while Q>1"?
//Initialise single source(G,s)
S=0
Q=V[G]
While Q != 0
Do u=extract-min(Q)
S=S union {u}
For each vertex v in adj[u]
Do relax(u,v,w)A. While loop gets executed for v times
B. While loop gets executed for v-1 times
C. While loop gets executed only once
D. While loop does not get executed
Answer: Option B
This Question Belongs to Data Structure >> Graph Algorithms (DFS, BFS, Dijkstras, Etc)
Join The Discussion