0

I will like to know if anyone has an idea on the concept behind point to point route generation on google maps and nokia maps. What logic was used to determine the route and generate directions from any point on the map to another? I wouldn't mind guesses or something of that sort. I just want to understand, how it works.

duncan
  • 31,401
  • 13
  • 78
  • 99
dubyzu
  • 49
  • 1
  • 4
  • Check this http://stackoverflow.com/questions/430142/what-algorithms-compute-directions-from-point-a-to-point-b-on-a-map – thebenman Jul 27 '16 at 13:44

2 Answers2

1

This is just a guess, but probably something like Dijkstra's algorithm. It most likely is some kind of graph-search algorithm, with each node representing an intersection and each edge representing a section of street.

Charles R
  • 441
  • 3
  • 4
  • I second this and with prim algorithm you find the shortest water grid or telecommunication grid. – Micromega Nov 04 '11 at 17:50
  • What language do you think Google and Nokia use to implement this? – dubyzu Nov 26 '11 at 00:12
  • @user1030144 Recently [Project open source routing machine](http://project-osrm.org/) came to life providing routing capabilities to open street map, and it's based in C++. – Caio Iglesias Oct 28 '15 at 09:23
  • good answer you can choose dijkstra algorithm. good answer here http://stackoverflow.com/questions/39256309/calculate-the-shortest-route/39256428#39256428 – Alex Filatov Aug 31 '16 at 21:39
0

I will also add that the graph here is likely also weighted, with each weight corresponding to how important the road is. For example, Interstate highways may have a greater weight than state highways, which have a greater weight than local roads, which have a greater weight than simple streets. Optionally, toll roads may have a lower weight than non-toll roads.

Peter O.
  • 32,158
  • 14
  • 82
  • 96