Dijkstra algorithm

Question

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|)$

Comments

a) O(v²)

Answer 1

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).$

Comments

In Dijikstra's algorithm at each step we need to pick the unvisited vertex with the min distance from the source. So, we need a suitable data structure for giving this.

---

Yes. That's the reason we use Heap data structure but here in the question we substituted the data structure with Sorted Linked list.

And you don't have to sort it explicitly, the Relax operation will take care of the sorting.

---

in dijkstra, we can generalise the TC as:  |V|*T(extract_min) + |E|*T(decrease_key)

   decrease key in sorted list will take O(V) time and extract min will take O(1) time

so Total = |V|*O(1) + |E| *O(V)

            =|V| + O(VE)

            = O(V^3) (|E| =|V|^2)