The Traveling Salesmen Problem

The Traveling Salesmen Problem (TSP) is as follows: given a set of cities, or vertices \( V \) a set of direct routes between cities, or edges \( E \) , and for each edge \( e \) a distance \( d_e \) , what is the shortest tour through all the cities that visits each city exactly once? As this problem is quite difficult, we often consider the special case where \( d_e \) is assumed to be metric, the metric TSP.