Consider the problem of finding a shortest (forward) path from an origin node s to a destination node t of a graph with given arc lengths, subject to the additional constraint that the path passes through every node exactly once.
(a) Show that the problem can be converted to a traveling salesman problem by adding an artificial arc (t, s) of length -M, where M is a sufficiently large number.
(b) (Longest Path Problem) Consider the problem of finding a simple forward path from s to t that has a maximum number of arcs. Show that the problem can be converted to a traveling salesman problem.