Greedy-approach
October 26, 2023GATE 1997
October 26, 2023Greedy-approach
|
Question 22
|
The time required to find shortest path in a graph with n vertices and e edges is :
|
O(e)
|
|
|
O(n)
|
|
|
O(e2)
|
|
|
O(n2)
|
Question 22 Explanation:
→ We can use dijkstra’s algorithm to find shortest path in a graph with n vertices and e edges is O(ElogV).
→ We know that E ≤ V2 if graph is complete and time complexity is O(n2)
→ We know that E ≤ V2 if graph is complete and time complexity is O(n2)
Correct Answer: D
Question 22 Explanation:
→ We can use dijkstra’s algorithm to find shortest path in a graph with n vertices and e edges is O(ElogV).
→ We know that E ≤ V2 if graph is complete and time complexity is O(n2)
→ We know that E ≤ V2 if graph is complete and time complexity is O(n2)