# 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:

1. 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] < shortest_distance and not visited[v]:
shortest_distance = distances[v]
shortest_vertex = v

if shortest_vertex == -1:
return [distances, predecessors]

for v in range(len(graph)):
edgeweight = graph[shortest_vertex][v]
if edgeweight != 0 and not visited[v]:
pathdist = distances[shortest_vertex] + edgeweight
if pathdist < distances[v]:
distances[v] = pathdist
predecessors[v] = shortest_vertex

visited[shortest_vertex] = True


1. 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

for v, d in graph[min_vertex]:
if not visited[v]:
if (distances[min_vertex] + d) < distances[v]:
distances[v] = distances[min_vertex] + d
predecessors[v] = min_vertex
heap.decreaseKey(v, distances[v])
visited[min_vertex] = True

return [distances, predecessors]

class Heap():

def __init__(self):
self.array = []
self.size = 0
self.pos = []

def swapNode(self, u, v):
temp = self.array[v]
self.array[v] = self.array[u]
self.array[u] = temp

def minHeapify(self, index):
smallest = index
left = 2*index + 1
right = 2*index + 2
if left < self.size and self.array[left] < self.array[smallest]:
smallest = left
if right < self.size and self.array[right] < self.array[smallest]:
smallest = right
if smallest != index:
self.pos[self.array[smallest]] = index
self.pos[self.array[index]] = smallest
self.swapNode(smallest, index)
self.minHeapify(smallest)

def extractMin(self):
if self.isEmpty() == True:
return
root = self.array
lastNode = self.array[self.size - 1]
self.array = lastNode
self.pos[lastNode] = 0
self.pos[root] = self.size - 1
self.size -= 1
self.minHeapify(0)
return root

def isEmpty(self):
return True if self.size == 0 else False

def decreaseKey(self, v, dist):
i = self.pos[v]
self.array[i] = dist
while i > 0 and self.array[i] < self.array[(i - 1) // 2]:
self.pos[self.array[i]] = (i-1)//2
self.pos[self.array[(i-1)//2]] = i
self.swapNode(i, (i - 1)//2 )
i = (i - 1) // 2;

def isInMinHeap(self, v):
if self.pos[v] < self.size:
return True
return False



Here's the graph of the runtime against the number of vertices v: • I don't see E in the graph?you are increasing the number of vertices V without showing the no of edges E in each case?
– ShAr
Sep 19 at 17:16
• @ShAr it's a complete graph, so E = V*(V-1)/2 Sep 20 at 2:30
• Python is quite the highlevel language. A benchmark that barely runs 300ms isn't exactly useful. Then your algorithms differ when it comes to early termination (in favor of the unsortedArr-implementation). And last but not least unless you feed both algorithms their individual worst-case input, the results won't reflect worst-case behavior.
– Paul
Sep 20 at 7:13
• 1-Try to add a counter in both to see how many times u iterated in the loop aside from any other influence, 2- try a couple of simple examples to make sure both codes produce correct output. I honestly kind of busy minded to trace the code correctness myself now but no one else had notified u of an error so if there's one then it's not that obvious in a fast read
– ShAr
Sep 20 at 8:47
• quick tip def isEmpty(self): return True if self.size == 0 else False Could be replaced by def isEmpty(self): return (self.size==0) Sep 20 at 9:33

Here is a worst-case example of a complete graph where the heap.decreaseKey() operation executes on every edge:

Let the vertices be $$V = \{1,2,\dotsc,n\}$$. The edge set $$E$$ is such that for every vertex $$i$$ and $$j$$ such that $$i, there is an edge of unit weight if $$j = i+1$$; and there is an edge of weight $$2(n-i)$$ if $$j > i+1$$.

Run the heap-based Dijkstra's algorithm on this graph with source vertex $$1$$. It will decrease the distance of the vertex $$j$$ every time it traverses the edge $$(i,j)$$. Moreover, it will take $$\Theta(\log |V|)$$ time for each call to heap.decreaseKey() operation as per the aggregate analysis. Therefore, the time complexity will be $$\Theta(|V|+|E|) \log |V|$$. Compare its performance with unsorted array based approach. You will see the difference.

Note that here, the shortest path tree is $$1$$ -> $$2$$ -> $$3$$ -> $$\dotsc$$ -> $$n$$.

• @Meowser Did you experiment with the above example? Did you observe the difference? I just want to know... Sep 20 at 13:48
• Yes, I experimented with a worst case complete graph as you described. For this case, the unsorted array approach does have a better performance than the heap-based algorithm. Thank you. Sep 20 at 14:00

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.

• Actually I did use random edge weights and source vertices during testing. The decreaseKey() operation does indeed take some time but it seems the time taken is too small compared to the rest of the function. The searching of the unsorted list seems to contribute the most to the time difference. Sep 20 at 8:36

In short: Your test sample is too small or unvaried.

The $$O$$ notation allows for arbitrary multiplicative and additive constants everywhere, and for edge cases in the input data (i.e., a list being sorted vs. unsorted vs. sorted backwards etc. could introduce very unexpected results; and it does not need to be obvious either).

For things like this I would design some test program which runs for a long time (minutes at least), is pretty random, and varies the input data meaningfully. This may or may not be hard to achieve; sometimes it's best to grab your data from "out of the system" to avoid your test case generator algorithm to somehow mesh with the algorithm under test and thus always generating "special" data.

Finally; if you are not designing your algorithm in thin air - i.e., if it's not library code but some application solving a real problem - then by all means test with a large sample size of your actual domain data. That way, you can actually exploit those edge cases in the complexities and the algorithm. For example, a Dijkstra-style algorithm pathfinding in OpenStreetMap real world data might just need different optimization than, say, a similar algorithm finding paths for a game character on a board of square or hexagonal fields...

• OpenStreetMap is big enough that Dijkstra will be very painful. The idea is still quite relevant - OSM is a good example of an almost-planar graph, where A* beats Dijkstra by a large margin. On a random graph, A* isn't nearly as good. Sep 20 at 8:20
• Yup, a negative result is a result too, @MSalters, so testing those algos in real world applications is very important. When I studied CS (decades ago) the only pathing algorithm I learned was Dijkstra, with no mention of practicability (but I do like it for its didactic value, and I guess it is the basis for more advanced algorithms). I then learned about A* when programming my first (simple/trivial/not worth mentioning) game.
– AnoE
Sep 20 at 8:28