wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

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.

flag
Suggest Corrections
thumbs-up
1
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Transformations Involving Modulus
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon