Which algorithm computes the shortest path from a source node to all other nodes in a weighted graph using a priority queue?

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

Answer: (A)

This is about finding the shortest paths from one starting node to every other node in a weighted graph by always expanding the frontier with the smallest known distance. This is achieved by Dijkstra's algorithm, which uses a priority queue (typically a min-heap) to pick the next node with the smallest tentative distance. The process starts with the source at distance zero and all others at infinity, then repeatedly removes the closest node, relaxes its outgoing edges, and updates neighbor distances if a shorter path is found. The steps continue until every node has been settled, giving the shortest path from the source to all nodes as long as all edge weights are non-negative. This approach is efficient and specifically designed for single-source shortest paths with a priority-queue-driven frontier.

Bellman-Ford can handle negative weights and detects negative cycles, but it relaxes all edges many times rather than prioritizing the closest node, so it doesn’t use a priority queue. Floyd-Warshall computes shortest paths between all pairs of nodes, not just from a single source. Kruskal’s algorithm builds a minimum spanning tree, which is a different problem entirely.