[Routing] Fast Routing Engine - State of Play

[Tristram Gräbener]

> btw what is it anyway that guarantees the algorithm to find a/the shortest path in the end? if only higher level (shortcut) edges are expanded and lower ones are pruned, why aren't there any shorter paths that stay undiscovered?
> (plz excuse if this the wrong place to ask.. but this keeps puzzling me)

Well, it took me some time to really admit the result (even if the
demonstration is not very complicated in Geisberger's thesis
http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
theorem2 page 30)

Get your optimal path in the normal graph: (u1...un)
Get the smallest node v of this path and consider the sub-sequence
(u,v,w), with u>v and w>v. During the contraction phase, you added the
edge (u,w) because this is the only real rule of CH, so you can leave
v out of your path.
Apply that recursively.
You will have a path where the first part is only increasing, and the
second part is only decreasing.

The second part will be explored by the backwards search, so from the
point of view of this search, you will also explore only higher nodes.

So, there is a guarantee to find the shortest path.

Just be careful on when you stop the search. Just when both searches
hit a common node, is not enough.

Maybe this wasn't very clear, but I least I tried :p