Time complexity for Dijkstra's algorithm with min heap and optimizations

Question

What is the time complexity of this particular implementation of Dijkstra's algorithm?

I know several answers to this question say O(E log V) when you use a min heap, and so does this article and this article. However, the article here says O(V+ElogE) and it has similar (but not exactly the same) logic as the code below.

Different implementations of the algorithm can change the time complexity. I'm trying to analyze the complexity of the implementation below, but the optimizations like checking visitedSet and ignoring repeated vertices in minHeap is making me doubt myself.

Here is the pseudo code:

// this part is O(V)
for each vertex in graph {
  distanceMap[vertex] = infinity
}

// initialize source vertex
minHeap.add(source vertex and 0 distance)
distanceMap[source] = 0
visitedSet.add(source vertex)

// loop through vertices: O(V)?
while (minHeap is not empty) {

  // Removing from heap is O(log n) but is n the V or E?
  vertex and distance = minHeap.removeMin
  if (distance > saved distance in distanceMap) continue while loop

  visitedSet.add(vertex)

  // looping through edges: O(E) ?
  for (each neighbor of vertex) {
    if (visitedSet contains neighbor) continue for loop

    totalDistance = distance + weight to neighbor
    if (totalDistance < saved distance in vertexMap) {

      // Adding to heap is O(log n) but is n the V or E?
      minHeap.add(neighbor and totalDistance)
      distanceMap[neighbor] = totalDistance
    }
  }
}

Notes:

• Each vertex that is reachable from the source vertex will be visited at least once.
• Each edge (neighbor) of each vertex is checked but ignored if in visitedSet
• A neighbor is added to the heap only if it has a shorter distance that the currently known distance. (Unknown distances are assumed to have a default length of infinity.)

What is the actual time complexity of this implementation and why?

Answer 1

1. Despite the test, this implementation of Dijkstra may put Ω(E) items in the priority queue. This will cost Ω(E log E) with every comparison-based priority queue.

2. Why not E log V? Well, assuming a connected, simple, nontrivial graph, we have Θ(E log V) = Θ(E log E) since log (V−1) ≤ log E < log V² = 2 log V.

3. The O(E + V log V)-time implementations of Dijkstra's algorithm depend on a(n amortized) constant-time DecreaseKey operation, avoiding multiple entries for an individual vertex. The implementation in this question will likely be faster in practice on sparse graphs, however.