title: What's the time complexity of Dijkstra's Algorithm
body: <pre><code>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) &lt; d[u]:
          d[u] = d[v] + w(v, u)
      S = S ∪ {v}
  </code></pre>
  
  <p>Note: ∈/ means not in, i can't type it in the code.</p>
  
  <p>This question maybe duplicates with some posts. </p>
  
  <p><a href="https://stackoverflow.com/questions/26547816/understanding-time-complexity-calculation-for-dijkstra-algorithm">Understanding Time complexity calculation for Dijkstra Algorithm
  </a></p>
  
  <p><a href="https://stackoverflow.com/questions/38772780/complexity-of-dijkstras-algorithm">Complexity Of Dijkstra's algorithm</a></p>
  
  <p><a href="https://stackoverflow.com/questions/26328860/complexity-in-dijkstras-algorithm">Complexity in Dijkstras algorithm</a></p>
  
  <p>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) </p>