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.

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

ReplyDelete@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.

ReplyDelete