3 ms·
First, note that this complexity is actually worse for highly dense graphs, where `m` (number of edges) dominates rather than `n` (number of nodes) [note that a
by o11c 1y ago
First, note that this complexity is actually worse for highly dense graphs, where `m` (number of edges) dominates rather than `n` (number of nodes) [note that a useful graph always has `m > n`, and often `m <= 2d n`, where `d` is the number of dimensions and the 2 is because we're using directed edges. Ugh, how do we compare log powers?].
Additionally, the `n` in the complexity only matters if for the Dijkstra approach you actually need a frontier of size proportional to `n` [remember that for open-grid-like graphs, the frontier is limited is limited to `sqrt(n)` for a plane, and for linear-ish graphs, the frontier is even more limited].
Also note that the "sorting barrier" only applies to comparison-based sorts, not e.g. various kinds of bucket sorts (which are easy to use when your weights are small integers). Which seems to be part of what this algorithm does, though I haven't understood it fully.
- lqet 1y agoVery 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.
- hinkley 1y agoSo that means it doesn’t work for Traveling Salesman, where the edges are nearly n^2? That might explain why it’s not been found before.