3 ms·
I was referring to variants of Customizable Route Planning. Easiest to implement is likely the partitioner of Sommer et al, and a unidirectional multi-level dij
by DennisL123 1y ago
I was referring to variants of Customizable Route Planning. Easiest to implement is likely the partitioner of Sommer et al, and a unidirectional multi-level dijkstra.
- n4r9 1y agoAh, I guess you mean this paper then: https://www.microsoft.com/en-us/research/wp-content/uploads/2013/01/crp_web_130724.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... There are many similarities between this approach and customisable contraction hierarchies. The latter allows a particularly elegant query-time algorithm involving only a couple of linear sweeps, I suspect even in the many-many scenario.
- DennisL123 1y agoYep, that’s the one. There are a number of follow-up papers that engineer individual aspects of the implementation.