How to find the shortest path between 2 points on a map?
 

If a user picks out their own position on a Google map (say), I'd like to figure the shortest path to another, particular point on the map.

I've been trying to figure this out, the idea that occurred to me was to break curves into small straight lines, but really not much more than that. (no idea even on how to measure the LENGTH of the lines after that! - er that'd be Pythagoras' theorem, right?)

Any heads on LQ wanna weigh in? :)

It's messy and complicated. There's one way streets. The shortest way in Ireland is often not the quickest way. In Ireland some of the big roads have the traffic but have QBCs (Quality Bus Corridors), which are lanes where only buses, bikes, and taxis are allowed. These operate near rush hour. Traffic lights abound, and are set randomly. Some short cuts (known as 'rat runs') have regular ramps of various sizes to prevent old people and kids from being mowed down by teenagers with 2 feet on the throttle. We drive on the left, so right turns are often limited. So the fastest routes are the routes where you can keep going.

Take all that stuff into account, and you'll do all right.

Everything said by business_kid is correct, for travel by road. Google Maps offers travel directions (for my part of the world) in four flavors: car, public transportation, bicycling, walking. Click on "walking" and you are likely to get the shortest path, other than a straight-line overland route.

Daniel B. Martin

Pittsburgh is so hilly that you have to consider 3 dimensions. Some streets right next to each other on the map are 200' apart vertically, so it can be very difficult even for a native to give directions.

None of you are talking about the ALGORITHM!

Is there any way for a program to access the Google Map "walking" data?

Maybe the google maps api helps https://developers.google.com/maps/?hl=nl

@smallpond: 200 feet? Wow. We have a place or two, Enniscorthy in Wexford is one that comes to mind, where they were built on the side of a hill. I stayed overnight with a motorbike and couldn't park outside the B&B. It just wouldn't hold on the stand.

The fact is, any algorithm or system fails to satisfy all. Listen to the stories about GPS devices.
Min has 'shortest distance,' or fastest route. I gather it thinks you do 500kmh on a motorway, because 'fastest route' it sends you by the main road to the motorway, and by the main road from the motorway. Shortest distance is suicidal outside the city limits. I got sent up farm entrances because it thought there was a way through the farmyard!

Google Maps sens me the most direct and SLOWEST way on a journey I do several times a week. I chug through villages with loads of traffic lights stacked against you, onto the longest queue in the area. Mind you Irish traffic is a disaster anyhow.

On my last visit to Pittsburgh, I tried to walk from downtown to the S 10th st bridge using just my general sense of direction (no map nor instructions). I had no idea you need to go through a tunnel and there was no useful sign at the point I though maybe I should turn right off of Forbes, but mistakenly decided turning right later would be better.

So I reached the Duquesne Athletic Field (which on a map is very near the bridge) and there finally found someone I could ask for directions. Those directions sent me down the scariest, decaying outdoor staircase I have ever been on (from Bluff St down to S 10th St).

Google maps shows that staircase. But if you ask for a walking route from the top of the staircase to the bottom, it sends you all the way back to the tunnel entrance. I don't really know whether the tunnel is correct either. I don't know if it has pedestrian access. Google maps is often wrong about that. There may be no safe way to walk to that bridge.

I don't know how to give advise on advanced algorithms to someone who is confused over the easy parts.

Try me. Yes, I *may* require some handholding, but only some. Whatever happens, I'm willing to go through the whole damn post of anybody who posts here, and SEE what I can make of it - I enjoy that adventure.

Map data is effectively a "directed graph" with a cost (expected time) for each link.

One basic approach to shortest path is:
1) Make a priority queue of all the nodes that can be reached in one step from the starting point, prioritized by low cost.

2) Repeatedly, take the lowest cost node from the queue and insert into the queue all nodes that can be reached in one step from that lowest cost node, that have not already been processed with a lower total cost.

When the destination node is pulled from the queue, you have found a short route to it. Depending on the rules of the map, it might be true that the first time you pull the destination node you have found the shortest route, or you might need to continue processing for a while (determined by characteristics of the map).

For real world maps, it is more efficient to either work in both directions at once (compute nodes with low cost to the destination at the same time you compute low costs from the source) or include a straight line minimum cost to the destination as part of the prioritization score.

Shortest path is a very well studied problem, so you can find rigorously defined algorithms very easily with a google search. I tried above just to give a beginner friendly description of the ideas.