[GraphHopper] bidirectional Dijkstra algorithm is not optimal

[Philipp Hamm]

Hi Peter,

yes I do, but it also occurs with CarFlagEncoder using the current master version.
with 0.2 the detour in 1.PNG does not occur, but instead the bidirectional algo chooses the same bypass as in 2.PNG



Von: Peter K [mailto:peathal at yahoo.de]
Gesendet: Donnerstag, 13. Februar 2014 21:19
An: graphhopper at openstreetmap.org
Betreff: Re: [GraphHopper] bidirectional Dijkstra algorithm is not optimal

Hey Philipp,

which version (or git commit) are you using and are you using custom encoders?

Regards,
Peter.

Hi everyone,

there seems to be a bug routing with bidirectional algorithms. I've got different routing results for same queries. (see attached pictures)
All bidirectional algos are picking suboptimal pathes sometimes.

For all I know A*-bidirectional is supposed to result in possible suboptimal routes, but dijkstrabi and dijkstraNativebi should find the shortest/fastest path.
The finish condition (currFromWeight + currToWeight >= nativeBestPath.getWeight()) should accept only for the best path or am I missing something?



Note: to replicate the attached routes you have to disable contraction hierarchies
here are the related URLs:
http://localhost:8989/?point=48.983206%2C12.140568&point=48.983438%2C12.136411&weighting=shortest&algorithm=dijkstra
http://localhost:8989/?point=48.983206%2C12.140568&point=48.983438%2C12.136411&weighting=shortest&algorithm=dijkstraNative
http://localhost:8989/?point=48.984428%2C12.144517&point=48.983146%2C12.136631&algorithm=dijkstra
http://localhost:8989/?point=48.984428%2C12.144517&point=48.983146%2C12.136631&algorithm=dijkstrabi





_______________________________________________

GraphHopper mailing list

GraphHopper at openstreetmap.org<mailto:GraphHopper at openstreetmap.org>

https://lists.openstreetmap.org/listinfo/graphhopper

-------------- n?chster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140214/9c16821a/attachment.html>