Which algorithm uses a priority queue to compute the shortest path from a source to all nodes in a weighted graph with non-negative weights?

Which algorithm uses a priority queue to compute the shortest path from a source to all nodes in a weighted graph with non-negative weights?

• A. Bellman-Ford
• B. Kruskal
• C. Dijkstra's
• D. Floyd-Warshall

Answer: (C)

Dijkstra's algorithm uses a min-priority queue to compute single-source shortest paths in a graph with non-negative weights. The idea is to always pick the unvisited node with the smallest known distance from the source, finalize that distance, and then update the distances to its neighbors (relaxation). Because all edge weights are non-negative, once a node is removed from the priority queue with its current distance, that distance is guaranteed to be the shortest possible from the source. The process repeats, gradually building the shortest paths to all nodes.

Other algorithms don’t fit this pattern: Bellman-Ford can handle negative weights and relies on repeatedly relaxing edges rather than selecting the next closest node via a queue; Kruskal finds a minimum spanning tree by processing edges in order, not shortest-path trees; Floyd-Warshall computes all-pairs shortest paths using dynamic programming without a priority queue.