GATE CS 2006 Q12 — Shortest Paths (Dijkstra, Bellman-Ford)

Dijkstra's algorithm is designed to find the single-source shortest path in a weighted graph. When the graph is unweighted (which is equivalent to all edges having an equal weight of $1$), the shortest path in terms of edge weights is simply the path with the minimum number of edges.

In this scenario:

• Dijkstra's algorithm simplifies to a standard Breadth-First Search (BFS).
• BFS explores the graph level-by-level, ensuring that when a vertex is first visited, the shortest path to it has been found.
• The standard data structure used to implement BFS is a Queue (First-In, First-Out).
• Using a Queue, the algorithm runs in $O(V + E)$ time, which is linear with respect to the size of the graph.

Why other options are incorrect:

• Stack: Used for Depth-First Search (DFS), which does not guarantee shortest paths.
• Heap: Used in Dijkstra's algorithm for general weighted graphs, resulting in $O((V + E) ext{ log } V)$ time complexity, which is super-linear.
• B-Tree: An external memory data structure, not suitable or efficient for standard in-memory shortest path traversals.

Thus, the correct option is (A) Queue.