3 ms·
Very good points. I wonder what this means for real-world street network graphs. In my experience, m can be considered proportional to n in road network graphs
by lqet 1y ago
Very good points. I wonder what this means for real-world street network graphs. In my experience, m can be considered proportional to n in road network graphs (I would estimate m ≈ 2C n, with C being between 2 and 3). This would mean that the asymptotic running time of this new algorithm on a classic road transportation network would be more like O(Cn log^2/3 n) = O(n log^2/3 n), so definitely better than classic Dijkstra (O(n log n) in this scenario). On the other hand, the frontier in road network graphs is usually not very big, and (as you also said for grid graphs) you normally never "max out" the priority queue with n nodes, not even close. I would be surprised if the ^2/3 beats the additional constant overhead of the new approach in this case.
- adgjlsfhk1 1y agoin the real world djikstra will definitely be faster.
- mananaysiempre 1y agoIt’s not often that you see O(E + V log V) Dijkstra with Fibonacci heaps, either, the O((E + V) log V) version with plain binary heaps is much more popular. I don’t know if that’s because the constants for a Fibonacci heap are worse or just because the data structure is so specialized.
- lqet 1y agoYes, a standard binary heap is very fast and incredibly simple to implement, mostly because you can store the entire heap in a single continuous array, and because you can access individual elements by simple pointer arithmetic. It's quite hard to beat this in practice.
- valenterry 1y agoIn real world you are not using either, you have way more way to optimize for a specific problem. For street networks you'd probably start with "A*" or something like that.
- clausecker 1y agoThe current meta game is the use of contraction hierarchies. Basically, you sinplify the network into hubs connected by trunk lines and then refine the routing close to start and destination.