Hacker News new | past | comments | ask | show | jobs | submit login

Contraction hierarchies[0] are a nice extension over which A* works even better and I believe these are used in osrm. I read a paper by Microsoft Research where they optimized the setting to enable shortest path routing in average of 5 memory reads, or something ridiculously unbelievable like that. [1]

0: https://en.wikipedia.org/wiki/Contraction_hierarchies

1: https://www.microsoft.com/en-us/research/wp-content/uploads/...




Related question: do you know how leveraged GPUs are in shortest path implementations and research?


The [1] paper contains a reference to PHAST https://www.microsoft.com/en-us/research/publication/phast-h...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: