[smokel]

Rome2Rio 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

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

[Sesse__]

Note 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]

Oh 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.