The Travelling Salesman Problem is one of the most popular and well-known problem in graph-theory requiring the most efficient Hamiltonian cycle. The problem is NP-hard.

### The problem

The Travelling Salesman Problem describes a salesman who has to travel between `N`

cities. The problem is to find the shortest possible route that contains every town exactly once and returns to the starting point.

### Solution

The simplest way is to generate all permutations (ordered combinations) and see which of them is **cheapest**. It is brute force search, so the time complexity of an algorithm is equal to `O(n!)`

. As you can probably guess, the sequential version of this algorithm will be incredible slow.

Multi-threaded version should works a little bit better. This program compares these two different approaches. We assume that the route starts and returns to city number 0. *Note:* a parallel solution uses OpenMP.

Source code available at GitHub.