The applet helps you learn and practice with three algorithms for solving the Traveling Salesman Problem: the Brute-Force, Nearest-Neighbor and Cheapest-Link algorithms.

Create Tab

Under this tab you create a weighted graph by dragging the cursor and by specifying the weights of the edges. The weights are modified by clicking on the numbers displayed a little off their vertical center line. If the Change Weights box is checked, the number will roll faster with the mouse button simply held down. When satisfied, switch to one of the three practice tabs.

Kruskal's algorithm is one way to construct a minimum spanning tree:

Brute-Force Tab

Brute-Force algorithm lists all the possible Hamilton circuits of the graph ordered by the magnitude of their weight. You can see and select any one of the circuits in the dropdown control at the lower right corner of the tab. The selected circuit is shown on the graph.

The number of Hamilton circuits on a complete graph grows as a factorial of the number of nodes (minus one), which is pretty fast. This is certainly a drawback of the Brute-Force method that is enumerates and lists all Hamilton circuits. For this reason, you should be using the algorithm with caution when the number of the nodes is above, say six or seven.

Nearest-Neighbor Tab

The Nearest-Neighbor algorithm starts at an arbitrary node and proceeds to any of the adjacent nodes of the minimum possible weight.

Cheapest-Link Tab

In the Cheapest-Link algorithm you select randomly any of the available edges of the minimum weight, with two caveats:

1. No circuits are allowed, except at the very last step, and
2. No three selected edges may be incident to the same node.