Register

GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm

127 views
1 1 vote

Consider Dijkstra's algorithm on a graph having $V$ vertices and $E$ edges.

Suppose an indexed priority queue is not used.

Instead, the tentative distances are stored only in an array $\text{distTo[ ]}$, and whenever the next vertex must be selected, the algorithm scans the array to find the unprocessed vertex having minimum distance.

Assume there are no self loops or parallel edges.

What is the asymptotic running time?

  1. $O(V+E)$
     
  2. $O(E\log V)$
     
  3. $O(V^2)$
     
  4. $O(VE)$

1 Answer

0 0 votes

Dijkstra's algorithm processes each of the $V$ vertices once.

Without a priority queue, finding the unprocessed vertex with minimum tentative distance requires scanning the $\text{distTo[ ]}$ array.

Each scan takes $O(V)$

Since this is done for all $V$ vertices, the total time for selecting vertices is:

$O(V \cdot V)=O(V^2)$

Relaxing all edges over the entire algorithm takes $O(E)$

Therefore, the total running time is $O(V^2+E)$

Since there are no self loops or parallel edges, the number of edges satisfies $E=O(V^2)$

Hence,

$O(V^2+E)=O(V^2)$

Answer $: \boxed{O(V^2)}$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
140
140 views
GO Classes asked Aug 29
140 views
GO Classes DPP | GATE CS, DA | Algorithms | Bellman Ford
Consider a simple version of Bellman-Ford algorithm where we initialize $\text{distTo}[s]$ to $0$ and the rest of $\text{distTo}[v]$ to $+\infty$. Then fix an order on al...
1 1 vote
1 1 answer
116
116 views
GO Classes asked Aug 29
116 views
GO Classes DPP | GATE CS, DA | Algorithms | Time Complexity
Suppose Huffman coding is implemented as follows.Initially, the $n$ symbols are stored in a min priority queue according to their frequencies.The algorithm repeatedly per...
1 1 vote
1 1 answer
144
144 views
GO Classes asked Aug 29
144 views
GO Classes DPP | GATE CS, DA | Algorithms | MST vs Shortest Path Tree
Consider the following statement:For every connected weighted graph $G$, there exists some vertex $v$ such that a shortest path tree rooted at $v$ is identical to a minim...
1 1 vote
1 1 answer
91
91 views
GO Classes asked Aug 29
91 views
GO Classes DPP | GATE CS, DA | Algorithms | Edge Relaxation
Consider a directed edge $e = v \to w$ with weight $7$. Suppose that during a shortest path algorithm:$\operatorname{distTo}[v] = 16$ and $\operatorname{distTo}[w] = 25$...