What's the time complexity of Dijkstra's Algorithm

Question

Dijkstra((V, E)):
  S = {}    //O(1)
  for each vertex v ∈ V:    //O(V)
    d[v] = ∞    //O(1)
  d[source] = 0    //O(1)
  while S != V:    //O(V)
    v = non visited vertex with the smallest d[v]    //O(V)
    for each edge (v, u):    //O(E)
      if u ∈/ S and d[v] + w(v, u) < d[u]:
        d[u] = d[v] + w(v, u)
    S = S ∪ {v}

Note: ∈/ means not in, i can't type it in the code.

This question maybe duplicates with some posts.

Understanding Time complexity calculation for Dijkstra Algorithm

Complexity Of Dijkstra's algorithm

Complexity in Dijkstras algorithm

I read them and even some posts on Quora, but still cannot understand. I put some comments in the pseudo code and tried to work it out. I really confuse on why it is O(E log V)

score 5 · Accepted Answer · answered Dec 13 '18 at 18:17

5

The "non visited vertex with the smallest d[v]" is actually O(1) if you use a min heap and insertion in the min heap is O(log V).

Therefore the complexity is as you correctly mentioned for the other loops:

  O((V logV) + (E logV)) = O(E logV) // Assuming E > V which is reasonable

answered Dec 13 '18 at 18:17

hbejgel

4,674
2
17
27

+like. nice answer. why "Assuming E > V which is reasonable" this is reasonable? – Nov 27 '20 at 04:32
A graph with fewer edges than vertices will have disconnected components which can be ignored for the purposes of the algorithm. – hbejgel Dec 03 '20 at 20:12

score 0 · Answer 2 · answered Jul 20 '19 at 09:57

0

it is O((V logV) + (E logV)) = O(logV * (V + E)) for general graphs.

You wouldn't just assume that the graph is dense i.e. |E| = O(|V|^2) since most graphs in applications are actually sparse i.e. |E| = O(|V|).

answered Jul 20 '19 at 09:57

timtody

139
1
6

What's the time complexity of Dijkstra's Algorithm

2 Answers2

Linked