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?
