# Shortest Path Problem? **URL:** \ **Category:** Factual Questions\ **Created:** [October 4, 2010, 3:04am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967 "2010-10-04T03:04:10Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![atomicbadgerrace](https://avatars.discourse-cdn.com/v4/letter/a/8e7dd6/32.png) [@atomicbadgerrace](https://boards.straightdope.com/u/atomicbadgerrace)\ **Post date:** [October 4, 2010, 3:04am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/1 "2010-10-04T03:04:10Z")
I’ll preface this by saying that I know little to nothing about Shortest Path problems. I vaguely remember covering the topic in a few computer science classes in college, but for the most part, I know nothing. Say I have a large network that resembles [something like this](http://imgur.com/qUa3G.png). In actuality, there are about 70 nodes and 150 edges. Given that the amount of time it takes to traverse each edge is known, what is the easiest way one could go about determining the most efficient path that passes through all of the nodes in the shortest amount of time? ---
**Author:** ![Fubaya](https://avatars.discourse-cdn.com/v4/letter/f/c2a13f/32.png) [@Fubaya](https://boards.straightdope.com/u/Fubaya)\ **Post date:** [October 4, 2010, 3:14am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/2 "2010-10-04T03:14:01Z")
Do you want to go back to the beginning after hitting all the points? If so, that would be a [Travelling Salesman Problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem). ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 4, 2010, 3:35am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/3 "2010-10-04T03:35:15Z")
The easiest way to find the exact answer is to try them all, which is not feasible. Wikipedia has a pretty good [section](http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms) on approximation algorithms for the TSP. ---
**Author:** ![atomicbadgerrace](https://avatars.discourse-cdn.com/v4/letter/a/8e7dd6/32.png) [@atomicbadgerrace](https://boards.straightdope.com/u/atomicbadgerrace)\ **Post date:** [October 4, 2010, 3:39am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/4 "2010-10-04T03:39:53Z")
_blink_ Thanks for the quick responses – and the points in the right direction. I was looking at Dijkstra’s algorithm, but the Traveling Salesman seems to be more fitting. It’s not necessary to hit each point exactly once, though – just at minimum (in fact, for this particular graph, hitting each point exactly once would be impossible). Given that I understand every other word on the Wiki description of the problem, what is a layman’s approach to applying it to this kind of situation? ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 4, 2010, 4:56am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/5 "2010-10-04T04:56:00Z")
First, you use Dijkstra’s algorithm to determine the shortest distance between any two arbitrary nodes in your graph, across all nodes. At that point, the solution for the layman consists of trying every possible permutation of nodes in the graph. For 70 nodes, that means checking 70!/2 possible permutations, which is equal to 5,989,285,834,984,945,898,036,391,860,844,549,368,229,469,071,273,212,928,777,681,432,314,004,791,394,922,659,840,000,000,000,000,000 distinct tests. ---
**Author:** ![atomicbadgerrace](https://avatars.discourse-cdn.com/v4/letter/a/8e7dd6/32.png) [@atomicbadgerrace](https://boards.straightdope.com/u/atomicbadgerrace)\ **Post date:** [October 4, 2010, 5:03am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/6 "2010-10-04T05:03:02Z")
> [@Punoqllads](#): > > First, you use Dijkstra’s algorithm to determine the shortest distance between any two arbitrary nodes in your graph, across all nodes. At that point, the solution for the layman consists of trying every possible permutation of nodes in the graph. For 70 nodes, that means checking 70!/2 possible permutations, which is equal to 5,989,285,834,984,945,898,036,391,860,844,549,368,229,469,071,273,212,928,777,681,432,314,004,791,394,922,659,840,000,000,000,000,000 distinct tests. Well, that doesn’t sound fun at all. I take it, then, there isn’t any application that will allow me to define the nodes, the edges, and spit out the optimum path? 😃 ---
**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:** [October 4, 2010, 5:21am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/7 "2010-10-04T05:21:05Z")
> [@](#): > > Thanks for the quick responses – and the points in the right direction. I was looking at Dijkstra’s algorithm, but the Traveling Salesman seems to be more fitting. It’s not necessary to hit each point exactly once, though – just at minimum (in fact, for this particular graph, hitting each point exactly once would be impossible). That’s still the traveling salesman problem. The only reason it’s usually expressed in terms of hitting every node exactly once is that it’s usually assumed that it’s a complete graph and that the points reside in a metric space, in which case it’s never necessary to revisit nodes. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 4, 2010, 5:25am UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/8 "2010-10-04T05:25:57Z")
> [@atomicbadgerrace](#): > > I take it, then, there isn’t any application that will allow me to define the nodes, the edges, and spit out the optimum path? 😃 Of course there is. The only issue is how patient you are. In all likelihood, somebody has made their implementation of an approximate TSP solver available under a generous license. Look for something like that, get a reasonably good solution, and call it done. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [October 4, 2010, 12:36pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/9 "2010-10-04T12:36:37Z")
> [@Punoqllads](#): > > First, you use Dijkstra’s algorithm to determine the shortest distance between any two arbitrary nodes in your graph, across all nodes. At that point, the solution for the layman consists of trying every possible permutation of nodes in the graph. For 70 nodes, that means checking 70!/2 possible permutations, which is equal to 5,989,285,834,984,945,898,036,391,860,844,549,368,229,469,071,273,212,928,777,681,432,314,004,791,394,922,659,840,000,000,000,000,000 distinct tests. Dijkstra’s algorithm is completely irrelevant. It’s TSP all the way. ---
**Author:** ![atomicbadgerrace](https://avatars.discourse-cdn.com/v4/letter/a/8e7dd6/32.png) [@atomicbadgerrace](https://boards.straightdope.com/u/atomicbadgerrace)\ **Post date:** [October 4, 2010, 3:34pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/10 "2010-10-04T15:34:49Z")
I can’t seem to find an implementation online that allows me to define my own edges. The few that I found allow me to define nodes, but then assume that each node is permitted to have a connecting edge to any other node – which is not the case. Any ideas? ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 4, 2010, 4:06pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/11 "2010-10-04T16:06:36Z")
As I mentioned above, you can use Dijkstra’s algorithm to compute the shortest distance between any two nodes in your graph. Then you have complete connectedness. ---
**Author:** ![ITR\_champion](https://avatars.discourse-cdn.com/v4/letter/i/c67d28/32.png) [@ITR\_champion](https://boards.straightdope.com/u/ITR_champion)\ **Post date:** [October 4, 2010, 4:23pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/12 "2010-10-04T16:23:59Z")
> [@atomicbadgerrace](#): > > I can’t seem to find an implementation online that allows me to define my own edges. The few that I found allow me to define nodes, but then assume that each node is permitted to have a connecting edge to any other node – which is not the case. > > Any ideas? Assuming that your edge weights are relatively small numbers, simply take all the pairs that are not connected on your graph and connect them with an edge of a billion. Then you’ve got an completely connected graph, but any shortest path that the implementation finds will miss the edges that are weighted a billion, so it won’t include edges that don’t exist on your original graph. ---
**Author:** ![panamajack](https://avatars.discourse-cdn.com/v4/letter/p/47e85d/32.png) [@panamajack](https://boards.straightdope.com/u/panamajack)\ **Post date:** [October 4, 2010, 4:25pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/13 "2010-10-04T16:25:25Z")
One thing of note is that if the measurements satisfy the Triangle Inequality, then some approximation algorithms are guaranteed not to be worse than a constant factor. That’s not necessarily a good reason to use them compared to one that may give better results, although it can work to provide a bound for your approximation. If you’re not sure what “satisfying the Triangle Inequality” means, in simple terms it’s the condition that it’s never faster to go to another node on the way if there’s a direct path connecting two nodes. A map where the nodes are cities and the “time” (or “cost”) of travel is just the distance between them is a good example. As for one that doesn’t satisfy it : If the time is based on, say airflight timetables, it may end up being faster to fly to Portland first, and then to Winnemucca, than to wait for the direct flight. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 4, 2010, 4:34pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/14 "2010-10-04T16:34:51Z")
One thing I forgot to mention – if you do use Dijkstra’s algorithm as a preprocessing step, you’ll want the program to not only spit out the distance between each pair of points, but also the path taken, so that when your TSP program spits out the resulting path you can then map it back to the actual edges traversed. ---
**Author:** ![bup](https://avatars.discourse-cdn.com/v4/letter/b/6bbea6/32.png) [@bup](https://boards.straightdope.com/u/bup)\ **Post date:** [October 4, 2010, 4:44pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/15 "2010-10-04T16:44:38Z")
One very crude approximation (that often works pretty well on well-connected networks) is to pick a node as an arbitrary starting point. Mark it visited. Find the closest node you can get to. Mark it visited. From there, find the closest node you haven’t visited yet, and keep repeating until you get to them all. A little bit more sophisticated, but totally doable, is the ant colony approach - [Ant Colony Optimization - Marco Dorigo, Thomas Stutzle - Google Books](http://books.google.com/books?id=_aefcpY8GiEC&printsec=frontcover&dq=dorigo&source=bl&ots=xswQd4bLpO&sig=p8BfcZvhyYAec11aCpr5wMFf39M&hl=en&ei=XASqTJCJA4Wvngensom5DQ&sa=X&oi=book_result&ct=result&resnum=11&ved=0CEIQ6AEwCg#v=onepage&q&f=false) - the Dorigo method. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [October 4, 2010, 6:42pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/16 "2010-10-04T18:42:58Z")
> [@Punoqllads](#): > > As I mentioned above, you can use Dijkstra’s algorithm to compute the shortest distance between any two nodes in your graph. Then you have complete connectedness. Please, please re-read the OP and the other follow up posts. You are completely and 100% totally **wrong** about using Dijkstra here. This is TSP and not actually Shortest Paths. The OP didn’t know the correct term. There is no reason for you to continue to mislead the OP on this. (And even if the OP was talking about SP, your posts still don’t make sense.) ---
**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:** [October 4, 2010, 6:57pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/17 "2010-10-04T18:57:13Z")
The Traveling Salesman problem assumes a complete graph. The OP’s graph is not complete, and so must be completed before any standard solution to the TS problem can be applied. One way to complete it is to use Dijkstra’s algorithm to find the shortest path between every pair of points, and to assign to the edge between those points that distance, as **Punoqllads** suggested. Another way would be to assign a huge distance to the edge between any two points not connected in the original graph, as **ITR Champion** suggested. **ITR** ’s suggestion is probably better, given that something like that is the the first step of the Dijkstra algorithm in the first place, but either method would work. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 4, 2010, 6:58pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/18 "2010-10-04T18:58:06Z")
> [@ftg](#): > > > [@Punoqllads](#): > > > > As I mentioned above, you can use Dijkstra’s algorithm to compute the shortest distance between any two nodes in your graph. Then you have complete connectedness. > > Please, please re-read the OP and the other follow up posts. > > You are completely and 100% totally **wrong** about using Dijkstra here. This is TSP and not actually Shortest Paths. The OP didn’t know the correct term. There is no reason for you to continue to mislead the OP on this. (And even if the OP was talking about SP, your posts still don’t make sense.) Here’s what I’m saying: say the graph has points A, B, C, and D, and edges AB length 2, BC length 3, CD length 4, and AD of length 6. The TSP programs that the OP has found assume a totally connected graph. But for this example there are no edges connecting A and C nor B and D. So, you use Dijkstra’s algorithm to calculate that the shortest distance from A to C is 5 (going through point B) and the shortest distance from B to D is 7 (going through C), and spitting out a list: A B 2 A,B A C 5 A,B,C A D 6 A,D B A 2 B,A B C 3 B,C B D 7 B,C,D C A 5 C,B,A C B 3 C,B C D 6 C,D D A 6 D,A D B 7 D,C,B D C 6 D,C Now you can put the first three columns of that list into the TSP program. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 4, 2010, 7:00pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/19 "2010-10-04T19:00:38Z")
> [@ftg](#): > > > [@Punoqllads](#): > > > > As I mentioned above, you can use Dijkstra’s algorithm to compute the shortest distance between any two nodes in your graph. Then you have complete connectedness. > > Please, please re-read the OP and the other follow up posts. > > You are completely and 100% totally **wrong** about using Dijkstra here. This is TSP and not actually Shortest Paths. The OP didn’t know the correct term. There is no reason for you to continue to mislead the OP on this. (And even if the OP was talking about SP, your posts still don’t make sense.) As I read it, what he’s suggesting isn’t incoherent. Given an incomplete graph with edge weights, if there’s no edge between vertices i and j, he wants to add an edge (i, j) with a weight equal to the weight of the shortest path between i and j. Then, whenever one of those edges shows up in the solution, simply replace it with the path. I’m not convinced that the shortest tour in this new graph will correspond to the shortest tour in the original graph, but it at least seems like a reasonable heuristic. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 4, 2010, 7:17pm UTC](https://boards.straightdope.com/t/shortest-path-problem/555967/20 "2010-10-04T19:17:05Z")
One place where **ITR Champion** ’s method breaks down is when you have a star network or a bunch of star networks connected by a backbone.