What is the traveling salesman problem?

It's the problem of finding the shortest possible route that visits a given set of cities exactly once each and returns to the starting city — a classic NP-hard optimization problem.

What is the Held-Karp algorithm?

It's a dynamic-programming algorithm that solves the traveling salesman problem exactly in O(n² · 2ⁿ) time by tracking the minimum cost to reach every (subset of cities visited, current city) combination, dramatically better than the O(n!) of brute force.

Does this find the optimal tour or just a good one?

The exact optimal tour — Held-Karp is not a heuristic or approximation; it's guaranteed to find the true minimum-cost tour, unlike faster heuristics such as nearest-neighbor or 2-opt.

Why is this solver limited to 12 cities?

Held-Karp's O(n² · 2ⁿ) time and space still grows exponentially — 12 cities keeps the computation comfortably instant in a browser, while covering the vast majority of hand-entered examples people want to solve exactly.

Does the distance matrix need to be symmetric?

No — this solver works with asymmetric distances (where the cost from A to B differs from B to A), which covers both simple symmetric road-distance examples and directional cases like one-way streets or flight costs.

What algorithm should I use for more than 12 cities?

Beyond the range where an exact solution is feasible, practical approaches switch to heuristics (nearest-neighbor construction, 2-opt or 3-opt local search, or genetic algorithms), which trade the optimality guarantee for speed on much larger instances.

How is this different from the Minimum Spanning Tree Calculator?

A minimum spanning tree connects every city with the least total edge weight but allows branching and doesn't need to form a single route; a TSP tour must be a single closed loop visiting every city exactly once, a much more restrictive requirement.

Where is the traveling salesman problem used in real life?

It's used in delivery and logistics route planning, PCB drilling and circuit board manufacturing, DNA sequencing, and as a benchmark problem for optimization algorithms in operations research.

Traveling Salesman Solver — Find the Shortest Route Through Every City

Our Traveling Salesman Solver finds the exact minimum-cost tour that visits every city exactly once and returns to the starting city, given a distance matrix between cities, using the Held-Karp bitmask dynamic-programming algorithm — an exact method deliberately scoped to at most 12 cities since the problem is NP-hard in general.

Quick Answer

Enter a distance matrix between cities to instantly find the exact shortest round-trip tour via Held-Karp dynamic programming.

Distance matrix

Enter one row per city, comma-separated distances, e.g. 0,10,15,20 then 10,0,35,25. Up to 12 cities.

How to Use the Traveling Salesman Solver — Exact Held-Karp DP Online

1
Enter a distance matrix, one row per city, with comma-separated distances, e.g. 0,10,15,20 then 10,0,35,25 and so on.
2
The matrix should be square, with each entry giving the distance between two cities (diagonal entries are typically 0).
3
Click 'Calculate' to find the exact optimal tour via Held-Karp dynamic programming.

Why Use Traveling Salesman Solver — Exact Held-Karp DP Online?

The traveling salesman problem asks for the shortest possible route that visits every city exactly once and returns to the start — a classic NP-hard problem where brute-force checking all (n−1)!/2 possible tours becomes impossible past a handful of cities. The Held-Karp algorithm improves dramatically on brute force using dynamic programming over subsets: it tracks, for every subset of visited cities and every possible ending city, the cheapest way to reach that state, building up from small subsets to the full set in O(n² · 2ⁿ) time instead of O(n!). That's still exponential, so this calculator caps the problem at 12 cities, where Held-Karp remains comfortably fast while still finding the exact, provably optimal tour (not just a good approximation).

Frequently Asked Questions

Related Tools

Hamiltonian Path Checker — Visit Every Node Once Online

Check whether a graph has a Hamiltonian path — a path visiting every node exactly once — via backtracking search. Free calculator, scoped to graphs of up to 10 nodes.

Minimum Spanning Tree Calculator — Kruskal's Algorithm Online

Find the minimum spanning tree of a weighted graph using Kruskal's algorithm. Free calculator with a simple edge-list input and union-find cycle detection.

Linear Programming Solver — 2-Variable Corner-Point Method Online

Solve a 2-variable linear program by finding and evaluating every corner point of the feasible region. Free calculator, maximize or minimize with linear constraints.