Algorithms for Finding Hamilton Circuits in Complete Graphs
Algorithms for Finding Hamilton Circuits in Complete Graphs
This Demonstration illustrates two simple algorithms for finding Hamilton circuits of "small" weight in a complete graph (i.e. reasonable approximate solutions of the traveling salesman problem): the cheapest link algorithm and the nearest neighbor algorithm. As the edges are selected, they are displayed in the order of selection with a running tally of the weights. An optimal solution can be displayed.