14
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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! $\endgroup$
    – Raphael
    Commented May 14, 2012 at 14:19

4 Answers 4

Reset to default
24
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Since the traveling salesman problem is normally about distance between cities, I'd have preferred an example with valid geometry. $\endgroup$
    – iCodeSometime
    Commented Oct 13, 2022 at 16:15
10
$\begingroup$

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,

Improve this answer
$\endgroup$
2
$\begingroup$

I have no idea how anyone here didn't notice that the application of Dijkstra's algorithm would be entirely unnecessary in this case? You could implement this greedy algorithm by simply selecting the closest node, which is known apriori. Dijkstra's algorithm is used for discovering paths, but you are only taking a single step each time. This obviously does not find the optimal solution to the TSP, but many very good approaches do not find it either. All optimal solution finders for TSP are very computationally demanding.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joe
    Commented May 9, 2012 at 18:25
  • $\begingroup$ 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. $\endgroup$
    – Joe
    Commented May 9, 2012 at 18:27
  • $\begingroup$ However, on a path, if we relax either of those constraints, then the problem is trivial. $\endgroup$
    – Joe
    Commented May 9, 2012 at 18:28
  • $\begingroup$ 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. $\endgroup$
    – JeffE
    Commented May 14, 2012 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.