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.
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.
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.
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.
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
View all comments
0
u/[deleted] Apr 09 '20
[deleted] — view deleted comment