[Introduction to Algorithms, CLRS] Exercise 1.1-4

This is a solution for Introduction to Algorithms. I write this for my study purpose.

1.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?

Similarity:

They are similar in the sense that both traverses a graph and tries to find out the path with minimum sum of the weights.

Difference:

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.

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.

source: http://atekihcan.github.io/CLRS/E01.01-04/

https://stackoverflow.com/questions/7763432/what-is-the-difference-between-travelling-salesman-and-finding-shortest-path