Algorithm Design and Analysis

4. A salesman plans to travel to several places where the distance between two places are given as follows:

If the salesman departs from A, and he wants to pass each place only once and return to A, please determine the shortest path for his travel and show the processin finding the result using Branch and Bound method and Dynamic Programming method.

\begin{tabular}{|c|c|c|} \hline From & To & Distance (km) \\ \hline A & B & 5 \\ \hline A & C & 2 \\ \hline B & A & 6 \\ \hline B & D & 8 \\ \hline C & A & 4 \\ \hline C & B & 7 \\ \hline C & D & 1 \\ \hline D & A & 7 \\ \hline D & B & 3 \\ \hline D & C & 9 \\ \hline \end{tabular}