Traveling Salesman Problem

The Traveling Salesman Problem (TSP) consists in finding a Hamilton Circuit on a weighted graph with the least total weight. The problem is usually posted on nearly complete graphs.

The applet below lets you practice with three algorithms used for solving the TSP: the Brute-Force, Nearest-Neighbor and the Cheapest-Link algorithms. The instructions for using the applet are available on a separate page and can also be read under the first tab directly in the applet.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at, download and install Java VM and enjoy the applet.

What if applet does not run?

(This applet was created to accompany Excursions in Modern Mathematics, Seventh Edition, by Peter Tannenbaum © Pearson Education. Reproduced with permission.)

The Brute-Force algorithm consists in simply listing all Hamiltonean circuits (if there are any) and choosing one (perhaps of many) with the least total weight. The Nearest-Neighbor algorithm forms a path, one vertex at a time, choosing a node joined to the previous one with an edge of the least possible weight. The Cheapest-Link algorithm picks edges almost randomly among those of the least weight, subject to two natural restrictions: there should not be three selected edges incident to the same node and no circuits should be formed until the very last step.

|Activities| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny