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

Question

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

2. 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) < 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][1] < self.array[smallest][1]:
            smallest = left
        if right < self.size and self.array[right][1] < self.array[smallest][1]:
            smallest = right
        if smallest != index:
            self.pos[self.array[smallest][0]] = index
            self.pos[self.array[index][0]] = smallest
            self.swapNode(smallest, index)
            self.minHeapify(smallest)

    def extractMin(self):
        if self.isEmpty() == True:
            return
        root = self.array[0]
        lastNode = self.array[self.size - 1]
        self.array[0] = lastNode
        self.pos[lastNode[0]] = 0
        self.pos[root[0]] = 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][1] = dist
        while i > 0 and self.array[i][1] < self.array[(i - 1) // 2][1]:
            self.pos[self.array[i][0]] = (i-1)//2
            self.pos[self.array[(i-1)//2][0]] = 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:

Answer 1

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<j$, 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$.

Answer 2

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.

Answer 3

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