Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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$ –  newbie Jan 30 '13 at 16:32
1  
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

1 Answer 1

up vote 1 down vote accepted

Your answer actually depends on what implementation of Dijkstra's algorithm is used. The textbook implementation inserts all nodes in the queue, and then proceeds with the extraction. The other starts with only the source in the queue. This is generally more efficient in practice, although it needs a bit of book-keeping.

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$.

share|improve this answer
    
The implementation I'm considering in the second one, I just insert 1 node at the beginning –  newbie Jan 30 '13 at 18:01
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.