2
$\begingroup$

My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?

Dijkstra algorithm pseudocode:

 1. Dijkstra(V, E, s):
 2.    Create an empty priority queue

 3.    for each v ≠ s:
 4.        d(v) ← ∞
 5.        d(s) ← 0

 6.    for each v ∈ V:
 7.        insert v with key d(v) into priority queue

 8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

My runtime analysis:

 1.
 2. O(1)

 3. O(n)
 4.     O(1)
 5.     O(1)

 6. O(n)
 7.     O(log(n))

 8. O(n)
 9.     O(log(n))

10.     O(m)
11.         O(1)
12.             O(log(n))
13.             O(1)

From my analysis, the largest runtime would be from lines 8, 10, 11, and 12, resulting in $O(nm\log(n)) \ne O((n+m) \log(n))$.

$\endgroup$
  • 1
    $\begingroup$ For reference, could you include your book's name? $\endgroup$ – Evil Jan 30 at 22:43
  • $\begingroup$ What analysis does the book give? Have you checked other sources? Dijkstra is utterly standard and analysed in about every AofA book. What you give there is an indented list of O-terms, not an analysis; have you tried a principled approach? $\endgroup$ – Raphael Jan 31 at 7:27
  • $\begingroup$ NB: Dijkstra's algorithm is not greedy. $\endgroup$ – Raphael Jan 31 at 7:27
1
$\begingroup$
 8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

Consider the multi-set of all edges that appear on line 10, where $u$ goes through all vertices thanks to the line 9 inside the while loop. There are two cases.

  • The graph is undirected. Each of those edges must be incident to a vertex $u$. So each edge in the graph appears exactly twice.
  • The graph is directed. Each of those edges must have $u$ as its starting endpoint. So each edge in the graph exactly appears once.

So in total, the number of edges that appear on line 10 is either $2|E|$ with undirected graph or $|E|$ with directed graph. So the running time from lines 8, 10, 11, and 12 is $2mO(\log(n))$ or $mO(\log(n))$. That is, $O(m\log(n))$.

Had the line 10 been For each edge (w,v) ∈ E:, your analysis might have had a chance to be correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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