I claim to have solved the travelling salesman problem as follows.

(You will have to be familiar with djikstra's algorithm for this.)

1) I am about to start using djikstra's algorithm on any given road network but,

2) The end node is not known for now, regardless, I just begin from any arbitrary node, assuming I will be given the end node at some later point in time or I will claim it myself.

3) At each step of djikstra's algorithm you stop me, I claim the last node I currently am to be the end node I was looking for. Also at each step I disregard the roads that has been travelled already for that particular path.

4)Whenever I get stopped, I am at the shortest path I can be from my initial node to the current node by virtue of djikstra's algorithm (end node from djikstra's perspective)

5) I continue the process unless I start to reach to every node.

6) There is only a final node remaining, I go there and still, the path I have chosen is shortest path possible from initial node to that node, and I have travelled all the nodes possible.

7) I return to the initial node, travelling through all the nodes with shortest path possible.

Question: why I haven't solved the travelling salesman problem?

P.S. please comment if my argument is not clear enough I will try to refine it. There is clearly a gap in my understanding of the theory and I want to understand what it is. I don't have enough CS experience to pose a question algorithmically.

  • $\begingroup$ I don't see any proof that your algorithm outputs the lowest-cost tour. As a first check, I suggest you try implementing it along with a known-good algorithm (e.g., brute-force), run both on a million randomly generated graphs, and see if your algorithm always gives the correct answer. $\endgroup$ – D.W. Sep 17 '19 at 21:25
  • $\begingroup$ I am claiming that my algorithm outputs the lowest cost tour by the virtue of djikstra algorithm. No matter whichever step you stop me while implementing djikstra, That would be the shortest route possible from my initial point to that point according to djikstra algorithm. Even if you stop me at the last node. That is the shortest path that can be travelled from my initial node to that previously specified 'last' node. And at this point I have been through all nodes hence solving the TSP? Are there any other holes you have found? I can discuss this more in chat. $\endgroup$ – Saugat Awale Sep 17 '19 at 21:28
  • 1
    $\begingroup$ You haven't solved the problem until you have a proof that (a) your algorithm always outputs the correct (optimal) solution, and (b) your algorithm runs in polynomial time. I don't see either in the question. I also find the specification of the algorithm unclear. I suggest specifying algorithms using pseudocode, rather than English. $\endgroup$ – D.W. Sep 17 '19 at 21:36
  • 2
    $\begingroup$ It doesn't matter that it is "the same as dijsktra". For \$1000000 prize, would it be too hard to write the pseudocode, no matter how similar it is to Dijsktra? And while you are at it, for \$1000000, it won't hurt you to actually implement the algorithm. Of course, you will discover that there is a difference between an algorithm in the tree and an algorithm in your hand. $\endgroup$ – Andrej Bauer Sep 18 '19 at 7:20
  • 1
    $\begingroup$ The proof burden is on you. You are proposing something that would be revolutionary if true. With high probability, and many many precedents, you are wrong and you are just using up our attention. Under these circumstances you are still unwilling to produce a couple of dozen lines of pseudo-code, and insist on waving your hands and asking us to prove you wrong. It doesn't work that way. We are willing to help and show you your mistakes, but you have to be willing to expand a bit of effort, too. We can't point to a mistake when it is obscured by inexact descriptions. $\endgroup$ – Andrej Bauer Sep 18 '19 at 12:47

3).. . Also at each step I disregard the roads that has been travelled already for that particular path.

In order to do that, you must be running Dijkstra on a graph with exponentially more vertices than the input graph.


Your algorithm builds a tree, not a single path.

  • $\begingroup$ I forgot to mention, I disregard the paths that have already been travelled and only chose the first 'path' that is able to fulfil the above problem, I disregard all the rest of the paths. $\endgroup$ – Saugat Awale Sep 17 '19 at 20:10
  • $\begingroup$ I have added an additional sentence in point number 3 $\endgroup$ – Saugat Awale Sep 17 '19 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.