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

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)

A method that uses a priority queue to always pick the currently closest unvisited vertex and then relaxes its outgoing edges is designed to compute the shortest paths from a single source to all other nodes in a graph with non-negative edge weights. It maintains a distance value for each node and keeps them in a min-priority queue based on these distances. Each step picks the node with the smallest distance, finalizes that distance, and updates neighboring nodes if a shorter path is found through it. This greedy selection ensures progress toward the true shortest paths and makes the overall process efficient, typically O((V + E) log V) with a binary heap. This approach is the one that specifically fits the use of a priority queue for single-source shortest paths. Other algorithms handle different goals or conditions: Bellman-Ford can handle graphs with negative edge weights and detects negative cycles but doesn’t rely on a priority queue; Floyd-Warshall computes shortest paths between all pairs of nodes with dynamic programming; Kruskal builds a minimum spanning tree, not single-source shortest paths.

A method that uses a priority queue to always pick the currently closest unvisited vertex and then relaxes its outgoing edges is designed to compute the shortest paths from a single source to all other nodes in a graph with non-negative edge weights. It maintains a distance value for each node and keeps them in a min-priority queue based on these distances. Each step picks the node with the smallest distance, finalizes that distance, and updates neighboring nodes if a shorter path is found through it. This greedy selection ensures progress toward the true shortest paths and makes the overall process efficient, typically O((V + E) log V) with a binary heap.

This approach is the one that specifically fits the use of a priority queue for single-source shortest paths. Other algorithms handle different goals or conditions: Bellman-Ford can handle graphs with negative edge weights and detects negative cycles but doesn’t rely on a priority queue; Floyd-Warshall computes shortest paths between all pairs of nodes with dynamic programming; Kruskal builds a minimum spanning tree, not single-source shortest paths.