Is it true that if we apply any single source shortest path algorithm for each vertex, it will turn into an all pair shortest path algorithm?

Question

For example, if I ran Dijkstra's algorithm for each vertex, would that produce the all pair shortest path for the entire graph like when running Floyd-Warshall?

I am leaning towards this being true with the caveat being that running the single source shortest path algorithm for each vertex is less efficient since it wouldn't utilize dynamic programming to avoid redundant computations.

Answer 1

Yes, you can produce the all pairs shortest paths. And it is faster compared to Floyd Warshall algorithm: For a graph consisting of n vertices and m edges, the complexity of Dijkstra for a single source is O(mlogn) if you use a binary heap. Therefore, for all pairs shortest paths the complexity is O(mnlogn). Floyd Warshall algorithm has complexity O(n^3).