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 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.
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.