Project ForgeAlgorithms
Graph Algorithms
GATE 2007
Easy
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
- ADijkstra's algorithm starting from S
- BWarshall's algorithm
- Cperforming a DFS starting from S
- performing a BFS starting from S
Explanation
In an unweighted graph, BFS finds shortest paths (in terms of number of edges) from a source in O(V+E) time — strictly faster than running Dijkstra's algorithm (designed for weighted graphs) or Floyd-Warshall (all-pairs, much more expensive), and DFS does not generally find shortest paths at all.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.