Travelling Salesman Problem – parallel implementation using OpenMP

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.