How are the shortest-path and traveling-salesman problems given above similar? How are they different?
They are similar in that they both deal with a map and care about the distance between points (cities and roads for example). Additionally, each problem seeks to produce a route that minimizes distance. They differ in that the shortest-path problem has a defined beginning point and end point with no stipulations on which or how many points must be traversed from beginning to end. The travelling salesman problem instead cares about hitting every destination along the way while ending at the original beginning point - this difference complicates the problem greatly.