Mastering Algorithms with C

Implementation and Analysis of the Traveling-Salesman Problem

To solve the traveling-salesman problem, we begin with a graph that is represented simply as a list of vertices. In this representation, an edge connecting every pair of vertices is implied. Each vertex in the list is a TspVertex structure (see Example 16.5). This structure consists of four members: data is the data associated with the vertex, x and y are coordinates for the point the vertex represents, and color is the color of the vertex.

The tsp operation begins by coloring every vertex white, except the start vertex, which is colored black and added to the tour immediately. The coordinates of the start vertex are also recorded so that we can compute distances between it and every other vertex during the first iteration of the main loop. In the main loop, we add all of the remaining vertices to the tour. During each iteration, we look for the white vertex closest to the last vertex. Each time we add a vertex, we record its coordinates for the next iteration and color the vertex black. After the loop terminates, we add the start vertex again to complete the tour.

The runtime complexity of tsp is O (V ²), where V is the number of vertices to visit in the tour. This is because for each of the V - 1 iterations of the main loop, we search the vertices in the graph to determine which is white and needs a distance computed to it. Notice that O (V ²) is quite an improvement over the runtime complexity for computing an optimal ...