Which of the following algorithms solves the single-source shortest paths ?

Answer: Dijkstra’s algorithm.

• Dijkstra’s algorithm: Solves the single-source shortest-paths problem for graphs with non-negative edge weights. With a binary heap or priority queue, the running time is typically about O((V + E) log V).

• Prim’s algorithm: Finds a minimum spanning tree, which is a different problem (connect all vertices with minimum total edge weight) and does not produce shortest paths from a source.

• Floyd–Warshall algorithm: Computes shortest paths between every pair of vertices (all-pairs) and can handle negative edge weights; it runs in O(n^3) time, so it is not the single-source algorithm asked for.

• Johnson’s algorithm: Also an all-pairs method that reweights edges and then runs a single-source algorithm (like Dijkstra) from each vertex. It is useful for sparse graphs but is not the direct single-source solver.

• Note on negative weights: If edge weights can be negative, use Bellman–Ford to solve the single-source shortest-paths problem instead of Dijkstra.