In an unweighted, undirected connected graph, the shortest path from a node S…
2007
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.
Dijkstra’s algorithm starting from S.
- B.
Warshall’s algorithm
- C.
Performing a DFS starting from S.
- D.
Performing a BFS starting from S.
Attempted by 173 students.
Show answer & explanation
Correct answer: D
Answer: Breadth-first search (BFS) starting from S finds the shortest path (measured in number of edges) from S to every other node.
Why BFS works: BFS explores vertices in layers of increasing distance (number of edges) from the source. The first time a vertex is discovered, it is reached via a shortest path in terms of edges.
How to implement: initialize distance[S] = 0, mark S visited, enqueue S. While the queue is not empty, dequeue a vertex u and for each unvisited neighbor v set distance[v] = distance[u] + 1, mark v visited, and enqueue v. Optionally record parent pointers to reconstruct paths.
Time and space complexity: Using an adjacency list, BFS runs in O(V + E) time and uses O(V) extra space for the queue and distance/visited arrays.
Comparison to other algorithms: Dijkstra’s algorithm is intended for weighted graphs (nonnegative weights) and is typically slower here; Floyd–Warshall (Warshall) computes all-pairs shortest paths in O(V^3) and is overkill; DFS does not guarantee shortest paths.
A video solution is available for this question — log in and enroll to watch it.