What is the difference between Travelling Salesman and finding Shortest Path?

The only difference I could think of for the question is that in the Travelling Salesman Problem (TSP) I need to find a minimum permutation of all the vertices in the graph and in Shortest Paths problem there is no need to consider all the vertices we can search the states space开发者_JAVA百科 for minimum path length routes can anyone suggest more differences.

---

You've already called out the essential difference: the TSP is to find a path that contains a permutation of every node in the graph, while in the shortest path problem, any given shortest path may, and often does, contain a proper subset of the nodes in the graph.

Other differences include:

• The TSP solution requires its answer to be a cycle.
• The TSP solution will necessarily repeat a node in its path, while a shortest path will not (unless one is looking for shortest path from a node to itself).
• TSP is an NP-complete problem and shortest path is known polynomial-time.

If you are looking for a precise statement of the difference I would say you just need to replace your idea of the "permuation" with the more technical and precise term "simple cycle visiting every node in the graph", or better, "Hamilton cycle":

The TSP requires one to find the simple cycle covering every node in the graph with the smallest weight (alternatively, the Hamilton cycle with the least weight). The Shortest Path problem requires one to find the path between two given nodes with the smallest weight. Shortest paths need not be Hamiltonian, nor do they need to be cycles.

---

With the shortest path problem you consider paths between two nodes. With the TSP you consider paths between all node. This makes the latter much more difficult.

Consider two paths between nodes A and B. One over D the other one of C. Let the one over C be the longer path. In the Shortest Path problem this path can get immediately discarded. In the TSP it is perfectly possible that this path is part of the over all solution, because you'll have to visit C and visiting it later might be even more expensive.

Therefor you can't break down the TSP in similar but smaller sub-problems.

---

Shortest path is just have source and target.we need to find shortest path between them obviously output must be tree in polynomial-time.

Finding Shortest Path:-

• Undirected graphs: Dijkstra's algorithm with list O(V^2)

• Directed graphs with arbitrary weights without negative cycles: Bellman–Ford algorithm Time complexity O(VE)

• Floyd–Warshall's Algorithm is used to find the shortest paths between between all pairs

TSP (Travelling-Salesman Problem) is not like that we have cover every node from source and finally we've reach source at minimum cost.Eventually there must be cycle. TSP is an NP-complete problem

Ref:

https://en.wikipedia.org/wiki/Shortest_path_problem

https://en.wikipedia.org/wiki/Travelling_salesman_problem

http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/

---

In TSP, you need to both visit all nodes and also return to your starting point. This complicates the problem immensely.