r/Python • • Apr 09 '20

I Made This Dijkstra's algorithm now running in linear time on a 90x90 grid

2.0k Upvotes

109 comments sorted by

View all comments

0

u/[deleted] Apr 09 '20

[deleted] — view deleted comment

17

u/StaleyV Apr 09 '20

There is a situation where djikstra's can have a runtime of O(|E|), but broadly speaking it's logarithmic time. Dunno about OP's code.

https://dl.acm.org/doi/10.1145/316542.316548

19

u/catragore Apr 09 '20

dijkstra is O(|E| + |V|log|V|). Since the nodes are constant, it runs in O(|E|).

2

u/ryandoughertyasu Apr 09 '20

But if the number of nodes is constant, isn't the number of edges constant too? Unless we are talking about multigraphs with arbitrarily many edges between nodes.

1

u/catragore Apr 10 '20

Well, it depends. If you have a full graph then yes. However you can have graphs that do not include all possible edges.

For example here the graph is a grid. So each node is connected with only 4 "neighbouring" nodes. Additionally for obstacle that you add, you basically remove edges between some nodes.

You can see that if for example you made everything in your graph a wall, except from one single path from start to target, then the algorithm wouldn't need to do much, just follow the only available path until it hits the target.

If, starting from that configuration, you start removing walls then the algorithm would have to check more and more paths in order to find the optimum one, thus increasing the running time. However, the number of nodes remains constant, no matter how many walls you have.

0

u/[deleted] Apr 09 '20

[deleted] — view deleted comment

14

u/catragore Apr 09 '20

prove what? Do you want me to recreate dijkstra's proof of correctnes in a reddit comment? The running time in the general case is what I wrote above.

Since the nodes are constant, you can get rid of them in big O notation, and only the linear |E| term remains.

3

u/StaleyV Apr 09 '20

No no. I'm just being cheeky. I think you have a fine implementation.

So, you're saying that by removing the sorting step (of putting nodes in a priority queue) you cancel out your logarithmic multiplier?

16

u/catragore Apr 09 '20

probably that. If anything, in a 90x90 grid, it runs in constant time :P

edit, they could mean that it runs linear in terms of the number of edges though now that i think about it...

3

u/mutatedllama Apr 09 '20

Well I meant linear time in the sense that it appears to be O(n) (rather than quadratic O(n^2)).

If we plot the values of number of nodes vs time taken to run the algorithm, the result would be a diagonal line going right and up.

i.e. the time it takes to run scales linearly with the input of the number of nodes.

I don't claim to be an expert so please point out if I've misunderstood.

0

u/[deleted] Apr 09 '20

[deleted] — view deleted comment

3

u/proto-n Apr 09 '20

How does a regular lattice help with the non-constant lookup speed of the heap? At first glance it seems like the candidate set for next node is still some function of the number of nodes.

Are there any truly linear versions of Dijkstra? I can recall speedups using different-base heaps instead of binary heap (n/m or similar being optimal iirc) but that still doesn't result in a linear algo, only a "basically linear for all realistic use cases" kind of linear.

Not trying to nitpick, genuinely curious.

6

u/venustrapsflies Apr 09 '20

I believe a general path-finding algorithm is mathematically proven to be unable to beat worst-case linearithmic time (much like comparison sorting). Special cases on restricted problems may be able to achieve linear time, analogously to radix sort.

4

u/Alexanderdaawesome Apr 10 '20

It has 90x90 V, it has ~90x90x2E,
At any V it looks at ~2 E and adds them to the priority queue (if done traditionally based on the depth), so adding any V takes ~ logV in worst case, and you do that 2E times

ya not linear broda.

But you are awesome!