This repository features two different programming approaches for solving TSP:

• brute-force and
• dynamic programming.

The solvers assume all cities are connected to each other. The city distances are passed using stdin, for example:

./tspsolver < input/20cities.in

The solver will give the shortest tour by returning a sequence of city indices (starting and ending with city 0), followed by the total length of the tour (i.e. the sum of all edges or distances):

0 9 16 5 10 15 13 6 19 11 17 3 14 7 1 8 2 12 4 18 0
369.99

The input for the solvers is defined by a simple distance matrix. Here's how to generate a randomized matrix with 20 cities and calculate it's shortest tour in a single line (using pee from moreutils for redirecting the generated distances to both stdout and the solver):

./genmatrix 20 | pee cat ./tspsolver