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>enSun, 26 Mar 2023 22:01:15 -0000