NOTICE: help.openstreetmap.org is no longer in use from 1st March 2024. Please use the OpenStreetMap Community Forum

# [closed] Shortest path problem from A to B on routing engines

 0 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 `nodeA_ID` and `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 ? asked 08 Apr '16, 19:07 shiro900 54●4●4●9 accept rate: 0% mmd 5.7k●1●53●88 1 "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." 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. (08 Apr '16, 19:29) alester @alester 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 (08 Apr '16, 19:32) shiro900 1 Well if your car is 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". (08 Apr '16, 20:44) Frederik Ramm ♦ @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. (08 Apr '16, 21:46) shiro900 @shiro900: why "google maps"? Did you hear of OSM already? ;-) Please use OSM! (08 Apr '16, 22:31) aseerel4c26 ♦ @seerel4c26 Oh yes, I will definitely try OSM! I just had the google maps already set up. (09 Apr '16, 09:30) shiro900 1 Same question was also posted here: http://gis.stackexchange.com/questions/188677/shortest-path-problem-from-a-to-b-on-routing-engines (09 Apr '16, 17:20) mmd showing 5 of 7 show 2 more comments

### The question has been closed for the following reason "Duplicate Question: another answer for the exact same question was already accepted on GIS StackExchange." by mmd 09 Apr '16, 17:22

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Question tags:

×305
×95
×6
×6
×3

question asked: 08 Apr '16, 19:07

question was seen: 2,431 times

last updated: 09 Apr '16, 17:22

### Related questions

NOTICE: help.openstreetmap.org is no longer in use from 1st March 2024. Please use the OpenStreetMap Community Forum