More on HW7: The Two Traveling Salesmen Problem

Hints:

Examples:

Let G have n vertices, named 1, 2, … n, in topological order. Thus, there is no edge (i, j) if i ≥ j.

Example 1: Let n = 20, and let G be a complete acyclic directed graph, i.e., there is an edge from i to j if and only if i < j. Let the weights {W (i, j)} be given by the following table; for example, W (1, 2) = 5. A blank entry means that W (i, j) is undefined, or ∞ if you prefer.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1  5 6 7 8 6 8 5 8 4 6 6 4 4 3 9 1 9 3 4
2  5 8 8 5 5 6 4 9 8 1 4 1 6 1 4 8 9 8
3  2 8 8 9 5 8 8 5 5 8 7 2 7 6 6 2 5
4  9 7 5 1 4 5 3 2 7 7 5 2 6 2 1 3
5  6 2 6 3 6 4 9 9 7 5 4 6 4 9 7
6  1 1 9 7 6 7 2 2 4 2 7 3 6 4
7  3 6 1 4 6 9 9 1 6 2 6 2 9
8  6 6 3 4 5 5 3 6 2 4 1 7
9  6 3 2 8 2 9 4 6 8 1 1
10  6 8 7 1 9 9 8 5 5 9
11  1 6 5 7 1 1 4 3 9
12  2 4 3 5 2 7 3 8
13  4 9 1 2 7 6 6
14  8 3 5 5 9 1
15  9 6 1 9 3
16  3 1 7 8
17  2 6 7
18  8 3
19  3

20

When I ran my progam with this input, I got the following output:

Start at 1
Move to 2 at cost 5
Move to 3 at cost 5
Move to 4 at cost 2
Move to 8 at cost 1
Move to 9 at cost 6
Move to 11 at cost 3
Move to 12 at cost 1
Move to 13 at cost 2
Move to 16 at cost 1
Move to 17 at cost 3
Move to 19 at cost 6
Move to 20 at cost 3
Start at 1
Move to 5 at cost 8
Move to 6 at cost 6
Move to 7 at cost 1
Move to 10 at cost 1
Move to 14 at cost 1
Move to 15 at cost 8
Move to 18 at cost 1
Move to 20 at cost 3
Total cost: 67