patternMajor
Dijsktra's algorithm applied to travelling salesman problem
Viewed 0 times
salesmanproblemapplieddijsktratravellingalgorithm
Problem
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.
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.
Solution
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:
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.
Here's a counter example where the greedy algorithm you describe will not work:
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.
Context
StackExchange Computer Science Q#1749, answer score: 24
Revisions (0)
No revisions yet.