# 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? Jan 30, 2013 at 16:29
• I mean that $(u,v)$ is the edge with less weight of all the edges of $G$
– abc
Jan 30, 2013 at 16:32
• As the problem is stated, the answer is not $\theta(n)$, but $O(1)$, since you already have the answer. Jan 30, 2013 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, 2013 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. Jan 30, 2013 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. Jan 30, 2013 at 18:29