How are the shortest-path and travelling-salesman problems given above similar? How are they different?
They are similar in the sense that both traverses a graph and tries to find out the shortest path with minimum cost (sum of the weights).
They are different because shortest-path problem finds a path between two points such that sum of the weights is minimized. Whereas, travelling-salesman problem finds the path covering all the points (start and end point is same) such that sum of the weights is minimized. Also, shortest-path problem is P complex and travelling-salesman is NP-complete.