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.
Let's say that I can somehow find the
(latitudeA, longitudeA) and
(latitudeB, longitudeB) 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
nodeB_ID 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.
However, a A' and B' must exist, very close to A and B respectively, so that the A'->B' path exists. So the routing engine should try and find that A'->B' path instead.
Also, that A'->B' path might not even be optimal. There could have been a A''->B'' path, where A'' and B'' were only a couple of meters away from A and B. So the routing engine should find the A''->B'' optimal path instead.
How do routing engines handle this situation ?