Friday, July 2, 2010

CLRS 2e: Exercise 1.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?
They are similar in that they are minimization problems but the difference is that the shortest-path problem just needs to minimize the distance between two points and the route in between doesn't matter but the traveling-salesman problem requires a path between multiple points and the route between them is the crux of the problem.


  1. Not necessarily!....In travelling salesman, the order of intersections is important

  2. @Anonymous Yes, that's why I said the route between the points in the travelling salesman problem is the most important part. In the shortest-path problem you don't care about the order or the overall route, you only care that it's the shortest path between two points.