Late last year there was a performance breakthrough in the task of calculating the most efficient route between 2 points in a network. One we've previously suspected impossible.
I now suspect there's more optimizations coming, now that we know its possible & we know where to look!
Earlier we often preprocessed the network to take shortcuts for certain network structures. Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, & Longhui Yin's optimization applies to any network, without preprocessing!
1/3
Duan, et al's optimization lowers the time complexity from O(m + nlogn) to O(mlog[2/3]n) for m edges (say, roads) & n nodes (say, intersections). Which is fairly significant improvement for a very common problem!
It is faster on any network of decent size, & no slower on smaller networks.
It is a divide & conquer algorithm which divides the network into reasonably sized graphs to apply the good old Dijkstra's Algorithm, or A* search, to.
2/3
The divide step scouts ahead a given number of nodes before recursing into the sub-networks. Whilst the merge step stitches the routing within those sub-networks back together.
It does require carefully designed datastructures prioritizing edge-nodes to merge for the performance win to eventuate. Which they achieve by optimizing for the fact that splitting will near-certainly give you closer edge-nodes to stitch together.
3/3 Fin!
@alcinnz I've come across their paper as well - absolutely amazing!
On Dijkstra's algorithm: I've recently learned about d-ary heaps, which are a generalization of binary heaps, where nodes have d children instead of 2. Paraphrasing Wikipedia:
Decrease priority ops are more performant at the expense of slower delete min ops, leading to better running times for algorithms such as Dijkstra's algorithm in which decrease priority ops are more common than delete min ops.
