Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The algorithm used by Google Maps?

  1. Feb 19, 2009 #1
    I was using at Google Earth, and used it to look at some directions when I noticed that program recommended that I take a right and drive down this road, then take a u-turn and drive past from where I turned originally, when I could've just simply taken a left instead.

    Does anyone know how Google Maps uses finds directions for someone? And, why would the application recommend that I take an unnecessary route like this? Is the software, by any chance, open-sourced as well?
  2. jcsd
  3. Feb 19, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    The general concept is called "djykstra algorithm" but most mapping systems have a few extra features on top.

    The map data might indicate no left runs allowed.
    Some routing algorithms, especialy for delivery trucks, are tuned to reduce left turns (I assume you are in a country that drives on the right) because these waste time and disrupt traffic flow.
    They are generaly biased to maximise the time you spend on major roads compared to minor ones - so a longer (distance) journey might be faster.
  4. Feb 19, 2009 #3


    User Avatar
    Science Advisor
    Homework Helper

    I noticed the same thing a few months ago when I had a training session in Columbus.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook