GATE CS 2007 Q41 — Shortest Paths (Dijkstra, Bellman-Ford)

For an unweighted, undirected connected graph $G = (V, E)$, the shortest path from a source node $S$ to all other nodes is measured by the minimum number of edges. We can analyze the efficiency of the given algorithms for this task:

• Breadth-First Search (BFS): BFS explores the graph level-by-level starting from $S$. The first time a node is visited during BFS, it is guaranteed to be reached via the shortest possible path. The time complexity of BFS is $\mathcal{O}(V + E)$, which is optimal (linear time).
• Dijkstra's Algorithm: Designed for weighted graphs with non-negative edge weights. While it can be used for unweighted graphs (by treating all weights as $1$), its time complexity is $\mathcal{O}(E + V \log V)$ (using a Fibonacci heap) or $\mathcal{O}((V + E) \log V)$ (using a binary heap), which is asymptotically slower than BFS.
• Depth-First Search (DFS): DFS explores as deep as possible along each branch before backtracking. It does not guarantee finding the shortest path in terms of the number of edges.
• Warshall's Algorithm: Used for finding the transitive closure of a graph (or Floyd-Warshall for all-pairs shortest paths), which runs in $\mathcal{O}(V^3)$ time and is highly inefficient for single-source shortest paths.

Therefore, BFS is the most efficient algorithm for this problem.