# What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.

What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with Dijkstra's algorithm using Binary Heap ?

To clarify, Dijkstra's algorithm is run from the source and allowed to terminate when it reaches the target. Knowing that the target is a neighbor of the source, what is the time complexity of the algorithm?

My idea:

Dijkstra's algorithm in this case makes $O(n)$ inserts ( $n$ if the graph is complete) and 1 extract min in the binary heap, before calculate the shortest path from $u$ to $v$.

In a binary heap insert costs $O(\log n)$ and extract min $O(\log n)$ too.

So the cost in my opinion is $O(n \cdot \log n + \log n) = O(n \log n)$

But the answer is $\Theta(n)$, so there is something wrong in my thinking.

Where is my mistake?

• What do you mean $(u,v)$ is the edge ... of $G$? Surely, $(u,v)$ cannot be an edge when you want to run Dijkstra's? – Pål GD Jan 30 '13 at 16:29
• I mean that $(u,v)$ is the edge with less weight of all the edges of $G$ – abc Jan 30 '13 at 16:32
• As the problem is stated, the answer is not $\theta(n)$, but $O(1)$, since you already have the answer. – Khaur Jan 30 '13 at 16:39
• In general, Dijkstra is not linear in the number of vertices, so it can't be a straight-forward application of Dijstra. – Raphael Jan 30 '13 at 17:08
• @newbie The complexity, as I hinted to above and that Khaur wrote, is $\theta(1)$, or the cost of checking the weight of the edge $(u,v)$. Your question makes sense if and only if you remove that sentence. – Pål GD Jan 30 '13 at 17:33

For the standard implementation, you can do better than $O(n \log n)$. Instead of successively inserting each node in the heap based queue, you create an array, and "heapify" it. "Heapify" is a bulk operation for converting a list of numbers into a heap, in $O(n)$, or rather $\Theta(n)$ (see here or here). After that, there will be only one/two extract-min operations (one or two depending on whether the source is originally in the queue or not) in $O(\log n)$. So overall, $\Theta(n)$.
For the other implementation, you can do it in $\Theta(\Delta \log \Delta)$, where $\Delta$ is the degree of the source $u$.
• @newbie Well in that case, you don't even need $\Theta(n)$. However, the answer makes more sense for the classical implementation, eg. on wiki or here. – Paresh Jan 30 '13 at 18:29