Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

A* can be tweaked to solve one-to-many shortest paths. You need to be careful about how you aggregate the heuristic function over all the targets [0]. Also, the performance improvements vs Dijkstra would practically disappear in many scenarios, for example if your source is "in the middle" of all the targets. In that case there's no benefit to biasing your search towards any particular target: you might as well simply expand outwards as you do in ordinary Dijkstra.

For road network routing (which is more my thing) you are orders of magnitude better off pre-processing the graph with contraction heirarchies [1] and then using a specialised algorithm such as RPhast [2] at query time.

[0] https://www.semanticscholar.org/paper/Heuristic-search-for-o...

[1] https://en.wikipedia.org/wiki/Contraction_hierarchies

[2] https://www.microsoft.com/en-us/research/publication/faster-...



Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

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

Search: