# Google Maps (& similar apps) Directions Algorithm **URL:** \ **Category:** Factual Questions\ **Created:** [May 2, 2019, 8:44pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389 "2019-05-02T20:44:32Z")\ **Posts on this page:** 13\ **Page:** 2
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 4, 2019, 5:48pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/21 "2019-05-04T17:48:59Z")
> [@enipla](#): > > For a trip to Oregon to New York, it does not need to look at all possible combinations, unless you want the shortest route, and then it will, I assume, do a buffer search of available roads for the shortest route as it starts working out a path. It should know that backtracking 20 miles is not a great idea unless it gets boxed in on the route. > > Not looking at traffic, the fastest route would be easier to calculate. Hmm, why would the algorithm differ between shortest and fastest? It’s just a different set of costs assigned to each road segment. ---
**Author:** ![enipla](https://avatars.discourse-cdn.com/v4/letter/e/54ee81/32.png) [@enipla](https://boards.straightdope.com/u/enipla)\ **Post date:** [May 4, 2019, 8:40pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/22 "2019-05-04T20:40:50Z")
> [@DPRK](#): > > Hmm, why would the algorithm differ between shortest and fastest? It’s just a different set of costs assigned to each road segment. That’s true. But I would hope it would take into account turns/stoplights/stop signs and such. That really slows you down. My department manages a road network. For emergency vehicles, we allow them to go on paved bike trails if they are wide enough. Also, we can take in how steep a hill is, or if it would be legal or possible for it to cross a median. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 5, 2019, 12:53am UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/23 "2019-05-05T00:53:08Z")
But turns/stoplights/stop signs and so on would, in the aggregate, just manifest as a different total weight for the road. So if two roads are both 35 MPH, but one has a lot more stoplights and side streets than the other, it might end up having a lower effective speed… but storing that effective speed in the database is no more difficult than storing 35 MPH would be. ---
**Author:** ![Melbourne](https://avatars.discourse-cdn.com/v4/letter/m/b5e925/32.png) [@Melbourne](https://boards.straightdope.com/u/Melbourne)\ **Post date:** [May 5, 2019, 5:47am UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/24 "2019-05-05T05:47:57Z")
> [@Fotheringay-Phipps](#): > > So I’m wondering if the changing recommendation is possibly due to the app recognizing that I’ve historically taken that route? Seems a bit far-fetched but these are mysterious matters … My preference is always to go past the gas station where I buy gas. It never remembers that. But I’m using a business-attached account, so it refuses to remember my travel history at all. (My guess is that people didn’t want their employers to have access to that kind of information). > [@GESancMan](#): > > So, for a more extreme example: suppose at 3:30 on a Friday afternoon, I ask Google Maps for directions from my home in Portland, OR to Boston. Does Google take the current rush-hour traffic in Chicago into account when calculating the route, and estimating the time the trip will take? If I leave the house at 7:30 AM, it directs me down the freeway. Not realizing that by the time I get to the city (8:30AM), that sucker is gonna be stationary at the city end. (I get all kinds of garbage for routes where Google doesn’t know that crossings or intersections exist, or where roads were blocked decades ago. Even worse for pedestrians ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 5, 2019, 1:19pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/25 "2019-05-05T13:19:04Z")
Here is a crazy idea for someone to falsify: perhaps part of the algorithm is to deliberately throw in some alternative routing, in order to continually probe the network and detect slowdowns, road closures, etc.? That is one hypothetical explanation as to why someone might be getting different directions for a routine daily drive, though it may be far-fetched. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 5, 2019, 3:02pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/26 "2019-05-05T15:02:10Z")
Alternately, if there are a bunch of people going between (roughly) the same points, you don’t want to put them all onto the same route, even if it is “best”, because then that one route would become so clogged that it wouldn’t be best any more. So you put 60% of the traffic on the route that’s 3 lanes each way, and 40% on the route that’s 2 lanes each way. ---
**Author:** ![obbn](https://avatars.discourse-cdn.com/v4/letter/o/d6d6ee/32.png) [@obbn](https://boards.straightdope.com/u/obbn)\ **Post date:** [May 5, 2019, 8:17pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/27 "2019-05-05T20:17:01Z")
What always cu guessed me about Google maps was that it would take me somewhere one tour then a totally different way on the return trip. Even late at night when traffic want as issue. Also, for the longest time I always wondered how Maps knows so much about local traffic conditions, knowing almost exactly where a slow up started in even the smallest street (indicated by green, yellow and red highlights in the route). Then it occurred to me, probably every Google phone that had location turned on is sending speed information to Google. It’s really quite amazing, especially something like me who spent 20 years as a Service Tech for BellSouth using paper maps to navigate. Young people have no idea how amazing this technology is, always being there for them. ---
**Author:** ![Baron\_Greenback](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/baron_greenback/32/48_2.png) [@Baron\_Greenback](https://boards.straightdope.com/u/Baron_Greenback)\ **Post date:** [May 5, 2019, 9:36pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/28 "2019-05-05T21:36:33Z")
> [@obbn](#): > > Then it occurred to me, probably every Google phone that had location turned on is sending speed information to Google. Yep, and on any route that has a decent amount of traffic and regular commuters it’s possible to infer a lot about traffic conditions. ---
**Author:** ![Pork\_Rind](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pork_rind/32/111_2.png) [@Pork\_Rind](https://boards.straightdope.com/u/Pork_Rind)\ **Post date:** [May 6, 2019, 12:47am UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/29 "2019-05-06T00:47:33Z")
> [@Baron\_Greenback](#): > > Yep, and on any route that has a decent amount of traffic and regular commuters it’s possible to infer a lot about traffic conditions. I saw a YouTube video that I probably have no hope of ever finding again where a guy was showing a line of stopped traffic on a local street and the corresponding red indication in Google Mpas. He then proceeded to hop on his motorcycle and lane split his way through that traffic at or near the regular speed limit. And then, because the sample size was small or whatever, the road then magically switched to green as the algorithm took his maneuver as indication that the traffic had cleared. That was the first time I realized that much of this traffic info is user generated. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 6, 2019, 1:18pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/30 "2019-05-06T13:18:32Z")
You can opt out of sharing your information with Google. But most people don’t bother to. What surprised me was once, I asked for directions from a certain point on the West Side to a certain point downtown, by bicycle. I knew how to get there, but I wasn’t sure which bridge-crossing would give me the shortest route (the Cuyahoga River separates the west side from downtown, so all routes must be channeled over one of a small number of bridges). What surprised me was that the downtown part of the route took all of the same unintuitive zig-zaggy turns that I would have taken, learned from long experience of which lanes are harder to cross over, and such. Until I realized that the population of people biking from the West Side to that particular destination downtown while carrying a droid probably consists mostly of me. ---
**Author:** ![bump](https://avatars.discourse-cdn.com/v4/letter/b/7c8e57/32.png) [@bump](https://boards.straightdope.com/u/bump)\ **Post date:** [May 6, 2019, 6:21pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/31 "2019-05-06T18:21:05Z")
> [@DPRK](#): > > Finding optimal paths through flow networks is really not that bad, algorithmically speaking; you shouldn’t have to “prune” anything (other than to satisfy weight constraints, roads only open during certain times of day, etc.) The real problem is to adapt to unpredictable traffic conditions in real time, and to do so accurately. Regular traffic patterns like rush hour should not present any special problems, I mean things like unexpected road closings. Prune might not have been the right word- I meant that it probably has some kind of way to identify routes that are already losing, and stops calculating any further. ---
**Author:** ![Spiderman](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/spiderman/32/230_2.png) [@Spiderman](https://boards.straightdope.com/u/Spiderman)\ **Post date:** [May 6, 2019, 10:49pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/32 "2019-05-06T22:49:10Z")
> [@DPRK](#): > > I have an old Garmin GPS that definitely has a settings option of fastest or shortest. In your situation of wanting to switch over mid-way I would have to manually change the setting mid-route, though. I know of that setting & have it set to fastest. What I’m talking about is needing it for the first mile (say you invited me over. I need directions out of your neighborhood back to the main road/interstate; after that I know the way home) & then just keeping it on after that but actually going my own route. Once I miss a turn, it keeps trying to route me back to that ‘missed’ road for some period of time, a mile or two. Eventually it gives up & decides that I’m so far along my ‘new’ route that it’s longer to go back to the way it wanted me to go & calculates a new route _but_ the ‘new’ route (my way) is now faster than the way it originally tried to take me. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 6, 2019, 11:48pm UTC](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389/33 "2019-05-06T23:48:19Z")
In that case I can only speculate that the GPS was cheating and the original “fastest” route was not the mathematically optimal fastest route— maybe it was indeed doing some “pruning” because the regular search algorithm was too slow for whatever reason and you had to get going. Or it could have been using some sort of A\* algorithm with a non-optimal heuristic; there are are a lot of possibilities (I presume the precise algorithm used is a secret). [Previous page](https://boards.straightdope.com/t/google-maps-similar-apps-directions-algorithm/833389.md?page=1)