3
$\begingroup$

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

enter image description here

$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – ShAr
    Sep 19 at 17:16
  • 2
    $\begingroup$ @ShAr it's a complete graph, so E = V*(V-1)/2 $\endgroup$
    – justhalf
    Sep 20 at 2:30
  • $\begingroup$ 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. $\endgroup$
    – Paul
    Sep 20 at 7:13
  • 1
    $\begingroup$ 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 $\endgroup$
    – ShAr
    Sep 20 at 8:47
  • $\begingroup$ quick tip def isEmpty(self): return True if self.size == 0 else False Could be replaced by def isEmpty(self): return (self.size==0) $\endgroup$ Sep 20 at 9:33
2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ @Meowser Did you experiment with the above example? Did you observe the difference? I just want to know... $\endgroup$ Sep 20 at 13:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – Meowser
    Sep 20 at 14:00
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Meowser
    Sep 20 at 8:36
0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – MSalters
    Sep 20 at 8:20
  • $\begingroup$ 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. $\endgroup$
    – AnoE
    Sep 20 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.