CODEWITHSUNDEEP
time-complexitydijkstra
user8314628
user8314628

Reputation: 2042

What's the time complexity of Dijkstra's Algorithm

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)

Upvotes: 4

Views: 6377

Answers (2)

timtody
timtody

Reputation: 149

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

Upvotes: 0

hbejgel
hbejgel

Reputation: 4837

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

Upvotes: 5

Related Questions