Dijkstra's Algorithm

Question

Let G(V,E) an undirected graph with positive edge weights . Dijkstras single source algorithm can be implemented using the sorted linked list data structure and adjacency list . What is the time complexity?

a) O(E|V|)

b)O(|V|^3)

c)O(|V|log|v|)

d)O((|E|+|V|)log|V|)

Comments

i think it is....O(E|V|) ???

---

Extract  min can be done in constant time sine LL is sorted, decrease key will take O(V) time

$T(n)=O(|V|*1+|E|*V) = O(VE)$

---

The answer which i am having is b .

so in my opinion the answer must be like (correct me if  i wrong)

Since the sorted linked list is given so we dont have to make one so O(1) for that.

Every time ( V times ) taking out minimum as V * O(1).

Find all edges adjacent to vertex by adjacency list = O(2E).

one time decrease key operation on every edge = E * decrease key operation on sorted link list

Decrease key operation on linked list = first reach the place where you have to perform decrease key operation (since no random access ) = O(V).

since this change can make list unsorted so 1 pass of bubble sort on the list = O(V) worst case.

total time on decrease key = O(V^2).

so , = O(V)+O(2E)+O(E*V^2).

---

@Abhinavg Bro this can actually be solved. Here I am assuming that node 0 represent distance to vertex 0, node 1 to vertex 1 and so on. Now see here we can mantain pointers to all the nodes of the list and then refer to those pointers when we want to perfom the decrease key operation. This would then take O(1) take. We can use this approach because we have limited number of nodes only so in extra O(n) space this can be done.

Hence we still would have complexity of EV.

Answer 1

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

for sorted linked list extract-min would take O(1) and Relax operation would take O(V).

Time complexity=O(V*time for one extract min + E* time for one relax operation)

                       =O(V*O(1) + E*O(V))

                       =O(EV)

This complexity is for sparse graph if dense graph then replace E by V^2

Option (A) is correct