0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Dec 13, 2014 at 6:07

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – hengxin
    Dec 13, 2014 at 2:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – jnalanko
    Dec 13, 2014 at 10:04

Your Answer

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

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