I am a novice(total newbie to computational complexity theory) and I have a question.

Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it?

From a start point we compute the shortest distance between two points. We go to the point. We delete the source point. Then we compute the next shortest distance point from the current point and so on...

Every step we make the graph smaller while we move the next available shortest distance point. Until we visit all the points.

Will this solve the traveling salesman problem.

migrated from cstheory.stackexchange.com May 9 '12 at 8:48

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    Note that TSP is NP-complete and Dijkstra's algorithm has polynomial runtime. What you propose would be next-to-trivial solution of the P=NP? question, so it is unlikely that your approach works. This kind of reasoning is only a heuristic, mind! – Raphael May 14 '12 at 14:19

Dijkstra's algorithm returns a shortest path tree, containing the shortest path from a starting vertex to each other vertex, but not necessarily the shortest paths between the other vertices, or a shortest route that visits all the vertices.

Here's a counter example where the greedy algorithm you describe will not work:

counter-example

Starting from $a$, the greedy algorithm will choose the route $[a,b,c,d,a]$, but the shortest route starting and ending at $a$ is $[a,b,d,c,a]$. Since the TSP route is not allowed to repeat vertices, once the greedy algorithm chooses $a,b,c,d$, it is forced to take the longest edge $d,a$ to return to the starting city.

As it already turned out in the other replies, your suggestion does not effectively solve the Travelling Salesman Problem, let me please indicate the best way known in the field of heuristic search (since I see Dijkstra's algorithm somewhat related to this field of Artificial Intelligence).

A heuristic algorithm can return optimal solutions (though the sizes it can manage are relatively small as a matter of fact) and the following method was suggested by Richard Korf in the 90s. While it works perfectly for the symmetric travelling salesman problem (where the cost of the edge $(u,v)$ equals the cost of the same edge when traversed in the opposite direction $(v,u)$), it can be easily adapted to the alternative case of the asymmetric version.

The best approach (I am aware of) consists of running a Depth-First Branch-and-Bound heuristic search algorithm where the heuristic is the cost of the Minimum Spanning Tree (MST). Since the MST can be computed in polynomial time with either the Prim's algorithm or the Kruskal's algorithm, then it can be expected to return solutions in a reasonable amount of time. For a wonderful discussion of these two algorithms I do strongly suggest you to have a look at The Algorithm Design Manual

As a matter of fact, let me highlight that since this approach was suggested not much progress have been seen in the field for deriving optimal bounds of this problem so that I do consider it to be a hot question in the field of combinatorial search.

Hope this helps,

The answer is no, that's not a good way of solving the TSP problem. A good counter example is where all the points are on a line, like the following:

--5------------------3-----1--0---2----------4

using Dijsktra's algorithm, would make the poor salesman starting at point 0, first go to 1 then to 2 then to 3 ect. which is not the optimal.

Hope that helps. Have a look at the first chapter in Steven S. Skiena excellent book called "The Algorithm Design" it explains this example in more detail.

The TSP problem is not finding the shortest way between two points, but in making a route between all the points which are optimal. When you have the optimal route you can use Dijsktra to find the shortest path between each points in the route.

  • 2
    Dijkstra is a single source shortest path algorithm, but it wouldn't "make" the salesman start at 0, nor would it return a route. It just returns the shortest path tree, containing the shortest path to each vertex from the given source vertex. – Joe May 9 '12 at 18:25
  • Traditionally, the TSP problem [en.wikipedia.org/wiki/… ] is "Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city." Technically it's not possible to satisfy those requirements on a path-- you must either not return to the starting city, or repeat cities. – Joe May 9 '12 at 18:27
  • However, on a path, if we relax either of those constraints, then the problem is trivial. – Joe May 9 '12 at 18:28
  • Of course, Dijkstra wouldn't make the salesman start at 0. But the algorithm proposed in the original question did not specify a start vertex; therefore, the proposed algorithm could force the poor salesman to start at 0. So this answer is correct. – JeffE May 14 '12 at 17:33

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.