2

Given a starting point A and an end point E, I need an algorithm to determine the minimum transit route in a city that passes through all points (A, B, C, D, E) and is the fastest possible. I know I can represent this problem in a graph, but I'm not sure which algorithm to use in this situation. I was thinking of using the Dijkstra algorithm, but it provides only the path between two vertices of the graph, without necessarily going through all the vertices.

Vinicius
  • 129
  • 1
  • 1
  • 2
  • 8
    You mean the traveling salesman problem? If so, good luck. – Becuzz Apr 15 '16 at 13:37
  • 1
    See also [Shortest path to visit all nodes](http://stackoverflow.com/q/33583392/427192) and [Wikipedia: Shortest Path Problem](https://en.wikipedia.org/wiki/Shortest_path_problem) – Dan Pichelman Apr 15 '16 at 14:15
  • One algorithm that gives great results in a good processing time is the [A* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm). – YuriAlbuquerque Apr 15 '16 at 20:17

3 Answers3

4

This is an NP-Hard problem

There has been lots of research on approximations to the TSP. You should look up "traveling salesmen approximations". These will be fast, but not guaranteed optimal/correct.

If you manage to solve this correctly/optimally in polynomial time, then you will be an eternal CS hero.

Tommy
  • 263
  • 2
  • 8
  • It's not very difficult if the condition is to pass points A, B, C, D, E in that order. It should also be polynomial if the maximum number of points to pass is fixed. – gnasher729 Apr 15 '16 at 18:40
  • 2
    @gnasher729 the latter part is certainly false. The TSP assumes the number of cities is fixed (not arbitrary). – Tommy Apr 15 '16 at 20:10
  • He wrote "the Dijkstra algorithm provides only the path between two vertices". So we have a huge graph, and want a path from A to E which passes through B, C, and D. Fixed = 3. Polynomial. – gnasher729 Apr 15 '16 at 22:34
  • @gnasher729: if the number of intermediate points is fixed, then the run-time is O(N + E), where N is the number of nodes and E is the number of edges. – kevin cline Apr 15 '16 at 23:11
  • @Tommy: the TSP does not assume the number of cities is fixed. It assumes that distance is pre-calculated for every city pair. The run time is exponential in the number of points to visited. – kevin cline Apr 15 '16 at 23:13
  • 1
    "He'll be a CS hero! A-Stars in his eyes!" – Mark H Apr 16 '16 at 01:45
1

As has been mentioned repeatedly, it is an NP-hard problem. If your problem is limited to 5 vertices, then you can most certainly brute-force your way to the solution as Eric Tressler mentioned above. I would like to add my own two cents, though, because I find hard problems to be fascinating...

If you wish your algorithm to be tractable, this solution will not do, because as the number of vertices in your graph grows, it will reach a point that will just be impossible for your algorithm to compute a shortest route within our lifetimes (or even the Universe's, depending on how any vertices your graph has). There are approximation algorithms for variants of the problem you might find interesting, though...

There is a 2-approximation (which in short means that it can be proven that the result this algorithm returns is at MOST 2 times the length of the actual optimal route... so it could actually return the real optimal route, something at most 2 times the length, or anything in between, depending on the input) algorithm for the metric traveling salesman problem. This is a special case of the Traveling Salesman problem where intercity distance satisfies the triangle inequality, so it isn't the exact same problem.

The assumption made is simply trying to enforce the triangle inequality (e.g. if you have triangle ABC, the shortest path between A and C is A-C as opposed to A-B-C. Here is the algorithm that works in polynomial time for metric TSP:

G - the graph G(V,E), where V is the set of vertices and E is the set of edges. C - cost function defined as C: E->N_o (the metric part... the cost for taking an edge)

ApproxMetricTSP(G, C):
    -Build a minimum spanning tree T (use Kruskal's or Prim's algorithms for
     this)
    -Run Depth-First-Search on T and keep track of the order in which the
     vertices are discovered
    -Return the cycle induced by the discovery order of vertices as H, the
     Hamiltonian cycle.

Building T takes time O(V^2).

The DFS part can be done in O(V), so the algorithm is O(V^2).

For more information, check out this link!

bitterman
  • 177
  • 6
-3

I'm assuming that you are looking for a slight generalisation of route planning: You have a large map with a huge number of possible connections, you want to drive from A to E (which Dijkstra's algorithm would handle), but you also want to touch points B, C and D.

Obviously you can run the "shortest distance" algorithm six times. You'd want to do better than that.

I'd start by ordering the six permutations of (B, C, D) according to the length of the straight line connection. Let's say the straight line connection A->C->D->B->E is shortest. You find the shortest route from A to C, C to D, D to B, B to E. Then you try the other routes, stopping the calculation when you can prove that the route will be longer.

There is a clever variation of the "shortest route" algorithm if you optimise distances only: You don't optimise the total distance, you optimise the difference between straight line and actual distance. If you plan a route from A to B, and one of the connections X->Y has a distance d, but going from X to Y brings you d' closer to the target B, then you count the distance d - d', not d.

With that variation, you will often be able to prove quickly that a connection will be longer than optimal. Say the straight line distance A->C->D->B->E is 15,725 metres, the shortest actual route is 17,290 metres, and the straight line distance for a different route A->C->B->D->E is 17,260 metres, then it is highly likely that you find quickly that touching the other points in that order will not be optimal.

Someone seems to insist that this is the "travelling salesman" problem. It's not, as you would realise if you actually read the question asked. It's exactly the problem that Google Maps routinely solves when you ask it for the shortest path from A to B while passing through some other points. It's about a map with thousands and thousands of roads, and a tiny number of locations to visit. The hard part of the problem is finding the shortest path from one place to another. Even if it was the "travelling salesman" problem: Why would I care that a problem is NP-complete if the problem size is 3?

gnasher729
  • 42,090
  • 4
  • 59
  • 119