In an unweighted, undirected connected graph the shortest path from a node S to every other node is computed most efficiently in terms of time complexity by
A
Warshall's algorithm
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
Performing a DFS starting from S
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
Dijkstra's algorithm starting from S
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
Performing a BFS starting from S
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution
The correct option is D Performing a BFS starting from S
In an unweighted graph performing a BFS starting from S takes O(n) time if graph contains n vertices.
Dijkstra's algorithm only find the single source shortest path and takes O(n2) time but it is good for weighted graph.
Warshall's algorithm for all pair shortest path takes (O3) time but is also applicable for weighted graph.