4 ms·
I don’t want to spam, but I’ve been using rome2rio website/app to find complex connections. They’re definitely not using this algorithm, but I’ve always been fa
by josefrichter 2y ago
I don’t want to spam, but I’ve been using rome2rio website/app to find complex connections. They’re definitely not using this algorithm, but I’ve always been fascinated that you get complex results almost immediately. I don’t know how they do it, but for me it’s one of the most fascinating works on the internet. Great job. [I’m not affiliated with them in any way]
- smokel 2y agoRome2Rio seems to find an optimal route, and the problem discussed in this post is about finding an optimal flow. Both are fascinating problems, but quite different. Finding shortest paths was typically solved with Dijkstra's algorithm [1], until someone discovered an amazing optimization scheme by precalculating some information that speeds up the search algorithm dramatically [2]. Thanks to this breakthrough, one can now interactively drag routes on Google Maps, for instance. And have Rome2Rio. [1] https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm [2] https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies
- Sesse__ 2y agoNote that there was not a step directly from Dijkstra to contraction hierarchies (CH); in particular, you could route using Highway hierarchies (HH) before CH came along. Both assume a fairly static network, though.
- smokel 2y agoOh yes, there have been many intermediate steps, it's a fascinating search in itself. I'd love to have a book detailing the history of shortest path algorithms. Let's hope Knuth has time to add it to TAOCP.