# Equivalence of Shortest Hamiltonian Paths to Traveling Salesman Problem

Two questions:

Q1- Why do we need to add "bidirectional" arcs (instead of single directional arcs) between the new node n + 1 and with every node in the original network?

Q2- Why is the shortest H-path problem on an n-node network G is equivalent to an (n + 1)-node TSP on network G'?

Q1. You need bidirectional arcs to and from the dummy node $$n+1$$ because you don't know ahead of time which directions are needed to complete the tour. Exactly one arc will enter the dummy, and exactly one arc will leave the dummy.
Q2. The two problems are equivalent because the H-paths in $$G$$ and TSP tours in $$G'$$ are in one-to-one-correspondence, with the same objective values. To go from H-path (with start $$s$$ and end $$t$$) to tour, insert arcs $$(t,n+1)$$ and $$(n+1,s)$$. To go from tour to H-path, remove the two arcs incident to $$n+1$$.