Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?

Based on theory, the implementation using adjacency matrix has a time complexity of E+V^2 and the implementation using min heap has a time complexity of (E+V)logV where E is the number of edges and V is the number of vertices.

When E>>V, such as for a complete graph the time complexity would be V^2 and (V^2)logV. This would mean that the implementation using min heap should be slower.

However I tested both implementations and found that the runtime for min heap is faster. Why is this so?

Here is my implementation:

• adjacency matrix and unsorted list

def dijkstraUnsortedArr(graph, start):
distances = [math.inf for v in range(len(graph))]
visited = [False for v in range(len(graph))]
predecessors = [v for v in range(len(graph))]
distances[start] = 0

while True:
shortest_distance = math.inf
shortest_vertex = -1
for v in range(len(graph)):
if distances[v]

• adjacency list and min heap

def dijkstraMinHeap(graph, start):
distances = [math.inf for v in range(len(graph))]
visited = [False for v in range(len(graph))]
predecessors = [v for v in range(len(graph))]
heap = Heap()

for v in range(len(graph)):
heap.array.append([v, distances[v]])
heap.pos.append(v)

distances[start] = 0
heap.decreaseKey(start, distances[start])
heap.size = len(graph)

while heap.isEmpty() == False:
min_node = heap.extractMin()
min_vertex = min_node[0]

for v, d in graph[min_vertex]:
if not visited[v]:
if (distances[min_vertex] + d) 0 and self.array[i][1]

Here's the graph of the runtime against the number of vertices v:

It depends on the input graph also. Perhaps, heap.decreaseKey() operation is not happening as frequently as it should. For example, consider a complete graph: $G = (V,E)$ such that all its edge weights are $1$.

In this case, the heap implementation will work faster since distance[v] for every vertex will be set to $1$ in the first iteration. The heap.decreaseKey() operation will not happen more than once on any vertex. Therefore, the complexity of the heap based approach here is $O(|E| + |V| \log |V|)$.

On the other hand, in the case of unsorted list approach, you will be computing the shortest distance $|V|$ times and computing it every time takes $\Theta(|V|)$ time. Therefore, in such a graph the time complexity of the unsorted list approach is $O(|E| + |V|^2)$.

You should check with your input graph. Try with random weights on the edges and random source vertex, then you will surely see that unsorted array approach will be better than the heap approach in the case of complete graphs.

StackExchange Computer Science Q#144059, answer score: 6