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. 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?
The easiest way to find the exact answer is to try them all, which is not feasible. Wikipedia has a pretty good section on approximation algorithms for the TSP.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.)
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.
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.
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.
