Landmark Weights vs Astar Bidir weights

[vghgh]

Hey guys!

I have 2 part question:
1)

So I am new to the ALT algorithm and I have read a few papers on it to understand it a bit better.

What I really want to understand is what really is how is the Landmark weight different from the Astar weights?

After digging through the code I can see that one uses the beeline and the other uses landmark. But after some further digging, at some point, don’t both these values converge or similar to one other(I am sure they don’t, but I am not able to quite understand this) ?

That is → if the landmark weight is really an approximation of the distance from the node to the target node, shouldn’t it always be smaller than the A* beeline approx weight (which might be more accurate?) ? And hence, at the best case scenario shouldn’t Landmark be as good as A*, as the weights are essentially the same in the best case for each ?

I am sure they are the same as the performance clearly says otherwise, so I would love to understand this!

So I loaded up Norcal osm, and I ran a bidirectional A* algorithm, using Landmark routing factory, for a specific route and I looked into the weights. Now when I wrote my own implementation of A* and used the landmark approximator, for the same node and the same target node I got different weights… And the weights were similar to the ones that I get with the beeline approximator.

It would be great if anyone could help me with these 2 questions! Thank you!

[easbar]

The main difference between the beeline approximation and the Landmark approximation is that the beeline approximation is purely based on, well, the beeline distance, while the Landmark approximation is based on the actual weights (let’s just say distances) of the routing graph. The actual distance is always larger or equal than the beeline, so it is the better approximation. If the target node is itself a Landmark the approximation is even exact / optimal. Since typically the target node is not a Landmark the algorithm uses one or more nearby Landmark nodes to estimate the distance based on the actual distances to the Landmarks and in most cases this is still a better approximation than the beeline.

and used the landmark approximator, for the same node and the same target node I got different weights…

Not sure what you mean here.

[vghgh]

Thank you so much for your clear explanation! I understand it now!
For some reason I thought landmark also stores euclidean distances rather than actual weights!