To implement Dijkstra’s shortest path algorithm on unweighted graphs so that…

Short answer: Use a FIFO queue (breadth-first search).

Why this works:

• On an unweighted graph, all edges have equal cost, so the shortest path is the one with the fewest edges.

• Breadth-first search explores vertices in order of increasing distance (layers). A FIFO queue enforces this layer-by-layer exploration.

• The first time a vertex is visited in BFS is via a shortest path (fewest edges) from the source.

Time complexity: Using a queue for BFS visits every vertex and edge at most once, so the runtime is O(V + E), i.e., linear in the graph size.

Note on alternatives:

• Using a heap (priority queue) is appropriate for weighted graphs but adds unnecessary overhead for unweighted graphs and prevents achieving linear time.

• A stack implements depth-first search and does not guarantee shortest paths.