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
• B. Performing a DFS starting from S
• C. Dijkstra's algorithm starting from S
• D. Performing a BFS starting from S

Answer 1

The correct option is D Performing a BFS starting from S

In an unweighted graph performing a BFS starting from S takes $O\left(n\right)$ time if graph contains n vertices.

Dijkstra's algorithm only find the single source shortest path and takes $O\left(n^2\right)$ time but it is good for weighted graph.

Warshall's algorithm for all pair shortest path takes $\left(O^3\right)$ time but is also applicable for weighted graph.