2,993 views
2 votes
2 votes

I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity)

But how ????
 

1 Answer

0 votes
0 votes
In the worst case scenario,i.e. in a complete graph, no. of edges become v(v-1)/2 i.e e~v^2.

Now,even with adjacency list implementation,which takes O(V + E),as E~V^2 , O(V+E)~O(V^2).

Related questions

1 votes
1 votes
1 answer
2
Souvik33 asked Dec 19, 2022
675 views
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE
1 votes
1 votes
1 answer
3
Jithin Jayan asked Jul 23, 2016
375 views
If a graph contains a positive weight cycle reachable from source, Can we find a well defined shortest path using Dijkstra/Bellman-Ford algorithm?
1 votes
1 votes
1 answer
4
Piyush Kapoor asked Nov 23, 2015
277 views
hi all ,Please tell me how much does dijkastra algoritm would take for unwaited and martix implementation