Graphs and NetworksSalesman

So far we have ignored the fact that some cities might be further apart than others. In real life, however, this is a very important consideration: we don’t just want to find any path but we want to find the shortest one. This is called the Travelling Salesman Problem. It has to be solved not only in transportation and logistics, but also when positioning transistors on microchips, to make faster computers, or when analysing the structure of DNA.

One simple method would be to try all possible paths, finding the length of each, and then picking the shortest one. However we have just shown that, even with just ${tsn2} cities there are ${tsn2}! = ${factorial(tsn2)} possible paths. Once you have hundreds or thousands of vertices, trying all possible paths becomes impossible, even using powerful computers.