edited by
2,485 views
4 votes
4 votes

Let $G(V,E)$ an undirected graph with positive edge weights. Dijkstra single source shortest path algorithm can be implemented using sorted linked list data structure. What will be time complexity?

  1. $O(|V|^2)$
  2. $O(|V|^3)$
  3. $O(|V|log|V|)$
edited by

1 Answer

Best answer
12 votes
12 votes
The answer should be option b.

The basic operations of Dijkstra's algorithm are extract-min and Relax(decrease key).

Now for sorted linked list extract-min would take $O(1)$ and Relax operation would take $O(V)$. And as we know the Relax operation will be applied on every edge so upper bound would become $O(VE)$.

Now in worst case $E=|V|^2$ , so time complexity $= O(V^2.V) =O(|V|^3).$
edited by

Related questions

0 votes
0 votes
0 answers
1
Elaf asked Jan 22, 2023
310 views
0 votes
0 votes
0 answers
2
gate20232 asked Jan 18, 2023
443 views
2 votes
2 votes
1 answer
3
1 votes
1 votes
3 answers
4
ankit_thawal asked Jan 25, 2018
1,477 views
I think answer should be Option(B).Path:<s,y><y,x><x,t = 7-3-2=2