Answers to: Shortest path problem from A to B on routing engineshttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines<p>I am in the process of creating a routing engine. I have encountered the following problem. Lets say the user gives a point A and point B and expects to get the A->B shortest path. I am using simple Dijkstra for now.</p>
<p>Let's say that I can somehow find the <code>(latitudeA, longitudeA)</code> and <code>(latitudeB, longitudeB)</code> coordinates, which are the closest coordinates to the A and B points that the user inputted. From those coordinates I could then also find the <code>nodeA_ID</code> and <code>nodeB_ID</code> on the graph. The problem is that for those nodes it is very likely that the A->B path doesn't exist at all. For example, if node A was only part of a one-way road that went to the opposite direction that the user wanted to go to.</p>
<p>However, a <strong>A'</strong> and <strong>B'</strong> must exist, <em>very close</em> to A and B respectively, so that the <strong>A'->B'</strong> path exists. So the routing engine should try and find that <strong>A'->B'</strong> path instead.</p>
<p>Also, that <strong>A'->B'</strong> path might not even be <strong>optimal</strong>. There could have been a <strong>A''->B''</strong> path, where A'' and B'' were only a couple of meters away from A and B. So the routing engine should find the <strong>A''->B''</strong> optimal path instead.</p>
<p>How do routing engines handle this situation ? </p>enSat, 09 Apr 2016 17:20:26 +0100Comment by mmd on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49133<p>Same question was also posted here: <a href="http://gis.stackexchange.com/questions/188677/shortest-path-problem-from-a-to-b-on-routing-engines">http://gis.stackexchange.com/questions/188677/shortest-path-problem-from-a-to-b-on-routing-engines</a></p>mmdSat, 09 Apr 2016 17:20:26 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49133Comment by shiro900 on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49129<p>@seerel4c26 Oh yes, I will definitely try OSM! I just had the google maps already set up.</p>shiro900Sat, 09 Apr 2016 09:30:37 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49129Comment by aseerel4c26 on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49126<p><a href="http://help.openstreetmap.org/users/12082/shiro900">@shiro900</a>: why "google maps"? Did you hear of OSM already? ;-) Please use OSM!</p>aseerel4c26Fri, 08 Apr 2016 22:31:27 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49126Comment by shiro900 on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49125<p>@FrederikRamm I think you might be right here. I will see how good my routing engine works once I implement it successfully so that I can visualize the results with google maps.</p>shiro900Fri, 08 Apr 2016 21:46:07 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49125Comment by Frederik Ramm on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49124<p>Well if your car <em>is</em> on the very long oneway road going in the wrong direction then it is little use to you if the routing engine says "hey, I found a point A' very near the point you are at, and from there the way is much shorter".</p>Frederik RammFri, 08 Apr 2016 20:44:59 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49124Comment by shiro900 on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49122<p><a href="http://help.openstreetmap.org/users/8189/alester">@alester</a> It doesn't have to be a dead-end. It could be a very long oneway road that would make you drive twice as long to go to your target location</p>shiro900Fri, 08 Apr 2016 19:32:45 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49122Comment by alester on shiro900's questionhttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49121<p>"The problem is that for those nodes it is very likely that the A->B path doesn't exist at all. For example, if that node was part of a one-way road that went to the opposite direction that the user wanted to go to."</p>
<p>In such a case, the shortest route would still exist but just go in a different direction. A dead-end oneway should never exist on the ground and only rarely occur in the data as a tagging error, so I wouldn't call it "likely". Assuming the data is generally correctly-connected, there should almost always be some way to route.</p>alesterFri, 08 Apr 2016 19:29:48 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines#49121