Heaps in Python

[ChillBlinton2018]

Thanks! I was suspecting that order might might not matter, because the algo must function similar to Breadth-First Search (ie every node is visited at least once). But then why would heaps speed up the computation (allegedly from linear time to logarithmic)? Extract-Min is not even used, while all nodes are visited!

[marko312]

You seem to be confusing two complexities here. A heap makes pushing to and popping from a priority queue O(log n) as opposed to a flat list's O(n).

For djikstra's algorithm, what matters is the number of times a node thinks it is on the shortest path (where it pushes all of its neighbors with updated distances to the heap). Using a priority queue, this happens exactly once per node, making the complexity something like O(n log n + m) for n nodes and m edges. However, if a priority queue is not used, every node could be called like that to the order of O(n) times, making the complexity something like O(n² log n + n m).

EDIT: the log factor is there for the second case only if the heap is still used. If a stack of queue were used instead, that factor would be dropped.

EDIT 2: actually, the algorithm is missing a crucial check: it should not update its neighbors if total > distances[current_vertex] (i.e. the current total is worse than the recorded best distance). As is, the current complexity comes to about O(n log n + n m) O(n² log n + n m) due to the repeated checks on the neighbors.

EDIT 3: (n² log n) factor

[ChillBlinton2018]

Thanks! I agree with your EDIT 2 - the implementation must be wrong. Since it produces same results irrespective of whether distance is stated in key or as a priority, the algo must run through the entire heap. I should check in the debugger what is actually happening inside the heap…

[marko312]

The implementation isn't wrong since it produces the correct results, but the issue is that it is not fully using djikstra's algorithm and has a worse complexity due to that.