4
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – John Kemeny
    Commented Jan 30, 2013 at 16:29
  • $\begingroup$ I mean that $(u,v)$ is the edge with less weight of all the edges of $G$ $\endgroup$
    – abc
    Commented Jan 30, 2013 at 16:32
  • 1
    $\begingroup$ As the problem is stated, the answer is not $\theta(n)$, but $O(1)$, since you already have the answer. $\endgroup$
    – Khaur
    Commented Jan 30, 2013 at 16:39
  • $\begingroup$ In general, Dijkstra is not linear in the number of vertices, so it can't be a straight-forward application of Dijstra. $\endgroup$
    – Raphael
    Commented Jan 30, 2013 at 17:08
  • $\begingroup$ @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. $\endgroup$
    – John Kemeny
    Commented Jan 30, 2013 at 17:33

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ The implementation I'm considering in the second one, I just insert 1 node at the beginning $\endgroup$
    – abc
    Commented Jan 30, 2013 at 18:01
  • $\begingroup$ @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. $\endgroup$
    – Paresh
    Commented Jan 30, 2013 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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