[GraphHopper] bidirectional Dijkstra algorithm is not optimal

[Philipp Hamm]

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

-------------- n?chster Teil --------------
Ein Dateianhang mit HTML-Daten wurde abgetrennt...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140212/9d040818/attachment.html>
-------------- n?chster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : 1.PNG
Dateityp    : image/png
Dateigröße  : 1134087 bytes
Beschreibung: 1.PNG
URL         : <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140212/9d040818/attachment.png>
-------------- n?chster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : 2.PNG
Dateityp    : image/png
Dateigröße  : 527920 bytes
Beschreibung: 2.PNG
URL         : <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140212/9d040818/attachment-0001.png>