Shortest Path Algorithms

Question

For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ?

a) run dijkstra's shortest path algorithm only once.

b) run dijkstra's shortest path algorithm V times.

What if the given graph is directed ?

Comments

you can run floyd warshall in both cases,running dijkstra will give you shortest paths to all vertices from a single source.and to find all pair shortest paths,u need to run dijkstra V times which is greater in time complexity than floyd warshall.

Answer 1

These complexities, are for Dense Graphs where Number of Edges is approx equals to V^2

General complexity of Dijkstra's Algorithm: O(E log V)

By applying Dijkstra V times, we can find all pair shortest path in O(V *V^2* log V) = O(V^3 log V)

By applying Bellman-Ford V times, we can find all pair shortest path in O(V * (V*E)) .= O(.V^4)

But By Applying Dynamic paradigm, Floyd warshall, its complexity =O(V^3)

Answer 2

you can run dijkstra  algo v times with complexity 0(v3log(v))

Answer 3

Run Dijkstra algorithm V times to get the all Pair Shortest Path.

Answer to the question related to directed and undirected graph: Dijkstra algorithm Relax each edge. And It does not really matter here, Because ones the all edges of a Vertex are relaxed, the vertex is deleted.