Dijkstra single-source shortest path $\Omega(n\log n)$?

Question

If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case?

I know heaps reduce Dijkstra's algorithm to $Ο(m \log n)$ and can be stored in an array. Rooted, binary, as complete as possible tree with all nodes satisfy Heap property: node <= all children of node.. Is this the right direction?

**I have an implementation that runs $O( (n + m)\log n),ドル could it work?

• D.W.: 1. It's standard convention to use $n$ to denote the number of vertices and $m$ the number of edges. Can you edit your question accordingly? As it stands this risks tripping up many people. 2. What precisely do you mean by $\Omega(n \log n)$? When there are two variables, big-O notation can potentially be misleading/misinterpreted unless you're very precise about what you mean.

Answer 1

Let $m$ be the number of vertices and $n$ the number of edges. The best you can get is $O(n + m \log m)$ by using a Fibonacci heap.

A Fibonacci heap allows decreasing the key of an element in amortized constant time. For each edge in the graph, Dijkstra's algorithm executes at most one decrease key operation. All these operations take time $O(n)$ in total. On top of that we have $m$ minimum extractions, which take time $O(m \log m)$ in total. Therefore the final complexity is $O(n + m \log m)$.

• hengxin: It is somewhat weird to denote the number of vertices by $m$ and the number of edges by $n$. I have totally misunderstood your answer at the first glance.
• jnalanko: I originally had the notation like that, but then I noticed that in the question it is the other way around, so I edited it because I thought it would be better to be consistent with the notation of the question.