The travelling salesman problem

This repository presents a C implementation that solves the classic Travelling Salesman Problem using both brute force and a graph-based approach.

Problem description

The travelling salesman problem (TSP) is a classic optimization problem. It asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

Solution

This repository offers two distinct approaches for solving the Traveling Salesman Problem (TSP). For detailed explanations of each approach, please refer to their respective folders.

Running the program

If you wish to test the program for yourself, follow the steps:

1. Download the repository to your local machine.
2. Open the folder of your chosen approach in your terminal.
3. Type make.

---

Updates

• August 26th, 2021: Initiation of the project development.
• December 13rd, 2021: Successful completion of the project.
• January 27th, 2024: Project translated and documented in English.

Further Information

The code presented in this repository was delivered as a project in the 'Data Structures I' course within the Applied and Computer Mathematics bachelor's degree @ ICMC-USP. The code was developed by Bianca Ângelo, Davi Fileti and Gabriel Penido in 2021.