Analysis of Algorithms : An Active Learning Approach

234 OTHER ALGORITHMIC TECHNIQUES

technique to find an approximate algorithm. The cost of traveling between cit-

ies could be represented by an adjacency matrix like the one in Fig. 9.1.^1

Our algorithm will go through the set of edges, picking them in order of

increasing weight. It will not be concerned about forming the path, but

instead it will make sure that edges added to the path meet two criteria:

1. They do not form a cycle with the other edges chosen unless all the nodes
   are in the cycle (in other words, we are done).


2. They are not the third edge connected to some node.
   For the example in Fig. 9.1, we would first choose the edge (3,5) because it
   has the smallest weight. We would then choose edge (5,6). The next edge to
   consider would be (3,6), but it would be rejected because it forms the cycle [3,
   5, 6, 3], which is not complete. Instead we would add the edges (4,7) and
   (2,7). The next edge to consider is (1,5), but it would be rejected because it is
   the third edge containing the node 5. We would then add the edge (1,6), and
   after that (1,4). The last edge to be added would be (2,3). This would give us
   the path of [1, 4, 7, 2, 3, 5, 6, 1] with a total length of 53. This is a good
   approximation but is clearly not the optimal solution because there is at least
   one path, [1, 4, 7, 2, 5, 3, 6, 1], which has a total length of 41.

(^1) This matrix is upper triangular because the cost of going from city i to city j is the
same as going in the other direction. If we were to store all of these values, we would
find the bottom half just a repetition of the top half. Using an upper triangular matrix
makes it easier to trace this algorithm.
From To 2
16
3
12
21
4
13
18
20
5
6
8
1
14
6
7
19
3
10
2
7
11
5
15
4
17
9
1 2 3 4 5 6
■FIGURE 9.1
The adjacency
matrix for a fully
connected
weighted graph