Dijkstra's algorithm is used to solve which type of problem in graphs?

• A. Graph coloring
• B. Shortest path between two nodes
• C. Sorting by key
• D. Minimum Spanning Tree

Answer: (B)

Dijkstra's algorithm is used to find shortest paths from a single source to other nodes in a weighted graph, assuming all edge weights are non-negative. It works by keeping track of the best known distance to every node and a tentative path, then repeatedly selecting the unsettled node with the smallest distance, finalizing it, and relaxing its outgoing edges to update neighboring distances. This greedy process guarantees that once a node is finalized, the path to it is the shortest possible. If you only need the path to a specific destination, you can stop once that destination is finalized; otherwise you can continue to obtain shortest paths to all nodes. The result is a shortest-path tree rooted at the source. This isn’t about graph coloring, sorting by key, or minimum spanning trees—the latter aims to connect all nodes with the minimum total edge weight, which is a different problem.