1,095 views
1 votes
1 votes
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 ?

3 Answers

1 votes
1 votes
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)
0 votes
0 votes

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. 

 

Related questions

1 votes
1 votes
3 answers
1
Rakesh K asked Nov 27, 2016
3,097 views
5 votes
5 votes
2 answers
2
jenny101 asked Oct 26, 2016
1,172 views
3 votes
3 votes
2 answers
3
dd asked Dec 6, 2016
2,604 views
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a sho...
1 votes
1 votes
1 answer
4
jenny101 asked Oct 26, 2016
564 views