Traveling Salesman Problem (TSP) – Optimized Implementations

This page features an interactive demo of the Traveling Salesman Problem (TSP), which I implemented in C with a focus on optimization. For this project, I developed four different versions, each demonstrating varying levels of efficiency—from a basic brute-force approach to a highly optimized solution using the Held-Karp algorithm with dynamic programming and bit masking. The most optimized version achieves a 200,000x speedup in CPU time compared to the naive approach with 13 cities, and this improvement would scale even further with more cities, I was unable to test that due to hardware limitations.

For this demo, I am showcasing the Held-Karp algorithm, which significantly reduces computational complexity compared to the naive approach. If you're interested in exploring the other implementations and their performance differences, visit the GitHub repository, where I provide a detailed breakdown, including benchmarking tables showcasing the speed improvements across versions.

Instructions

1. Under the white window below, enter the number of cities you want
2. Click "Generate cities" to generate random cities
3. Click "Show shortest path" to calculate the shortest path using the traveling salesman algorithm.
4. View results below demo!

Demo