title: Complexity of Dijkstra's Algorithm for Heap Implementation
body: <p>In CRLS' book, the analysis of Dijkstra's algorithm is as follows:</p>
  
  <p>How many times do you need to use the heap? One time for pulling off each node from the heap (i.e. Extract-Min in CRLS's book) --- O(N); and also every time when looking at the edge ---- O(E), you might need to change the distance (i.e., Decrease-Key in CRLS' book), which means to fix the heap order. And each heap operation needs O(logN) work. </p>
  
  <p><strong><em>Thus, total time complexity: O((N + E)logN), which is O(ElogN) if all vertices are reachable from the source.</em></strong></p>
  
  <p>My Question is:
  Why the complexity becomes O(ElogN) if all vertices are reachable from the source? Why can we ignore the O(NlogN) part from O((N + E)logN)?</p>