GATE CSE 2005 | Question: 38

Question

Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

• A. $O\left(|V|^2\right)$

• B. $O\left(|E|+|V|\log |V|\right)$

• C. $O\left(|V|\log|V|\right)$

• D. $O\left(\left(|E|+|V|\right)\log|V|\right)$

Comments

....

---

No reason for those many upvotes than the best answer

Dont miss:

 https://gateoverflow.in/1374/gate-cse-2005-question-38?show=187168#c187168

Adding to it

1. Unsorted arryay:

• EXTRACT_MIN = O(V)
• DECREASE_KEY = O(1)
• Dijkstra's => O(V^2 + E) = O(V^2)

2. Sorted array:

• EXTRACT_MIN = O(1)
• DECREASE_KEY = O(V)
• Dijkstra's => O(V + EV) = O(EV)

---

$$T(V, E) = \underbrace{O(V)}_{\text{Initialization}} + \underbrace{O(V)}_{\text{Heap Build}} + \underbrace{O(V \log V)}_{\text{Extract-Mins}} + \underbrace{O(E \log V)}_{\text{Relaxations / Decrease-Keys}}$$

$$T(V, E) = O((V + E) \log V)$$

Answer 1

Option $(D)$ :  Binary heap. $|E|$ decrease key operations and each taking $O\left(\log|V|\right)$ time $+$ $|V|$ extract-min operations each taking $O\left(\log|V|\right)$.

Option $(B)$ :  Fibonacci heap. $|E|$ decrease key operations and each taking $O(1)$ time $+$ $|V|$ extract-min operations each taking $O\left(\log|V|\right)$.

Option $(A)$ :  Array. Finding min-vertex in each iteration takes $O(V)$ and this needs to be done $|V|$ times.

Binomial Heap is same as Binary heap here, as the critical operations are decrease key and extract-min.

Correct Answer: $D$

Comments

@Aish

Yes binary heaps are either min heap or max heap but complexity depends on for what purpose you are using, here Dijsksta take min heap so that extract min can be done in Log v but if we take Max heap here then time complexity to extract min will be O(v) as min element can be any leaf of the tree

---

https://en.m.wikipedia.org/wiki/Dijkstra's_algorithm#Running_time

---

got it sir

Answer 2

1. Complexity Analysis:

   • Heap Insertion: Inserting all vertices into the heap initially takes O(V) time.
   • Extract-Min Operation: This operation, which finds and removes the vertex with the smallest tentative distance, is performed once per vertex. Since the extract-min operation on a binary heap is O(log⁡V), and it is performed V times, the total time for all extract-min operations is O(Vlog⁡V).
   • Decrease-Key Operation: This operation is performed each time an adjacency list is explored and the distance to a vertex is updated. This operation, which effectively updates the heap, takes O(log⁡V) per update. Since every edge may potentially lead to an update (in the worst case), and there are E edges, the total time for all decrease-key operations is O(Elog⁡V).

Combining these, the total time complexity for Dijkstra's algorithm using a binary heap becomes:

O(Vlog⁡V+Elog⁡V)=O((V+E)log⁡V)

2. Fibonacci Heap:

• Time Complexity: When using a Fibonacci heap in Dijkstra's algorithm, the extract-min operation still requires O(log⁡V) time, but the decrease-key operations are more efficient. The decrease-key operations in a Fibonacci heap can be done in amortized O(1) time.
• With the Fibonacci heap, the total time complexity breaks down as:
  • O(Vlog⁡V) for all the extract-min operations (since each vertex is extracted exactly once).
  • O(E) for all the decrease-key operations due to the amortized O(1) time per operation.
• Combining these gives a total of O(Vlog⁡V+E) time complexity.

Answer 3

dijkstra(G, S):
    for each node in V:
        disance[v] = ∞
    distance[S] = 0;
    
    Q = Heap();
    
    while Q is not empty:
        v = extractMIN(Q)
        
        for each adjacent u in V:
            if distance[u] < distance[v] + w:
                distance[u] = distance[u] + w
                parent[u] = v

 

Time Complexity of Dijkstra's algorithm here depends on two things 

1. To extract minimum from Heap: removing the minimum from Heap takes $O(logn)$ time.
2. Update for distance in Heap : each time we update the distance of key we have to check the position of node in Heap and reposition it can $O(logn)$ time

$T(n)$ =  $|V| ($remove minimum from Heap$) + deg(|V|)* ($update key$)$

 

$T(n)$ =  $|V| (log|V|) + 2|E|(log|V|)$

 

$T(n)$ =  $ |V|(log|V|) + |E|(log|V|)$

 

$T(n)$ =  $ O((|V|+ |E|) log|V|)$