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

@Gaurab @rude

but wikipedia it is O(V²)

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

And one question if it is unsorted what will be ur answer?

---

In an unsorted linked list, the cost of doing a build-heap is still O(|V|) because you need to create |V| different nodes or vertices. The cost of Extract-min is now O(|V|) because you have to do a linear scan over all the nodes(Vertices) in the list to find the minimum value. However, the cost of a decrease-key(Relax) is now O(1), since you can just update the node's key in-place.

This means that the runtime is O(V+ V.V+ E.1) [As Extract-min operation will be applied on every Vertex]= O(|V|+|V|² + E) = O(|V|²), since the number of edges is never more than O(|V|²).

---

Relax will be O(1) in unsorted why?

Sorted linked list also  relax is also in place, is not it?

---

For the case of sorted list the cost of doing a decrease-key(Relax) is O(|V|), since if you need to change a node's priority, you may have to move it, and you can't find where to move it without (in the worst case) doing a linear scan over the nodes as the list is SORTED.

But for UNSORTED list only the priority of the node is changed without moving it. Here when we are applying Extract-min operation we have to search the entire list to find the node with highest priority. But for SORTED list we just extract the first node as we know that is the highest priority node because in RELAX operation the node has been moved to its right place,i.e, the first position in the list.

---

@shrestha you are right. My bad. O(V^2) is the correct answer. O(V^3) is the time complexity of Bellman ford algorithm and as well as floyd warshall algorithm. Ty. bhai.

@Gaurab Check again.

---

Yes it will be for Unsorted. But for sorted it would be O(V³).

---

Yes, if we replace min-heap by a sorted linked list, we need to scan the entire array to determine the position of the vertices after each relax operation (to keep the list sorted). And this needs to be done for each edge. So, $O(EV) = O(V^3)$.

---

Thanks Arjun sir.

Is it clear now @Rude and @Shrestha?

---

ok @Gaurab means in sorted linked list first we have to sort it (you call it as priority) and then have to search the path. So, every edge and vertex we need to visit  , So complexity O(EV)

In unsorted we have to visit every vertex and and then relax , So, O(V²)

But why do u apply min heap?

---

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)