Visit Jeremy's Blog.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org How to find the shortest path between 2 points on a map?
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 01-05-2013, 07:51 AM #1 resetreset Senior Member   Registered: Mar 2008 Location: Cyberspace Distribution: Dynebolic, Ubuntu 10.10 Posts: 1,340 Rep: 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? Last edited by resetreset; 01-05-2013 at 07:54 AM.
 01-05-2013, 09:05 AM #2 business_kid LQ Guru   Registered: Jan 2006 Location: Ireland Distribution: Slackware & Android Posts: 8,866 Rep: 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.
01-05-2013, 10:02 AM   #3
danielbmartin
Senior Member

Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Mint 17.3
Posts: 1,646

Rep:
Quote:
 Originally Posted by resetreset 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.
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

 01-05-2013, 10:07 AM #4 smallpond Senior Member   Registered: Feb 2011 Location: Massachusetts, USA Distribution: CentOS 6 (pre-systemd) Posts: 2,923 Rep: 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.
 01-06-2013, 12:58 AM #5 resetreset Senior Member   Registered: Mar 2008 Location: Cyberspace Distribution: Dynebolic, Ubuntu 10.10 Posts: 1,340 Original Poster Rep: None of you are talking about the ALGORITHM! Is there any way for a program to access the Google Map "walking" data?
 01-06-2013, 04:29 AM #6 whizje Member   Registered: Sep 2008 Location: The Netherlands Distribution: Slackware64 current Posts: 592 Rep: Maybe the google maps api helps https://developers.google.com/maps/?hl=nl
 01-06-2013, 08:57 AM #7 business_kid LQ Guru   Registered: Jan 2006 Location: Ireland Distribution: Slackware & Android Posts: 8,866 Rep: @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.
01-06-2013, 09:52 AM   #8
johnsfine
LQ Guru

Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep:
Quote:
 Originally Posted by smallpond 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.
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.

Quote:
 Originally Posted by resetreset None of you are talking about the ALGORITHM!
Quote:
 Originally Posted by resetreset 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?)
I don't know how to give advise on advanced algorithms to someone who is confused over the easy parts.

Last edited by johnsfine; 01-06-2013 at 09:59 AM.

01-07-2013, 12:07 AM   #9
resetreset
Senior Member

Registered: Mar 2008
Location: Cyberspace
Distribution: Dynebolic, Ubuntu 10.10
Posts: 1,340

Original Poster
Rep:
Quote:
 Originally Posted by johnsfine 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.

01-07-2013, 07:29 AM   #10
johnsfine
LQ Guru

Registered: Dec 2007
Distribution: Centos
Posts: 5,286

Rep:
Quote:
 Originally Posted by resetreset 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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post resetreset Programming 3 05-20-2012 01:28 PM TheIndependentAquarius Programming 1 06-27-2011 03:37 AM Dennola4 Slackware 8 07-28-2009 02:14 AM ak.lokesh Linux - Newbie 3 02-19-2009 12:37 PM Electrode Linux - Software 0 05-30-2004 02:03 AM

LinuxQuestions.org

All times are GMT -5. The time now is 03:54 PM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -