Traveling Salesman (TSP) Solver
Solve the traveling salesman problem exactly for up to twelve nodes with Held–Karp, and print the optimal tour and its total distance.
Traveling Salesman (TSP) Solver
Solve the traveling salesman problem exactly for up to twelve nodes with Held–Karp, and print the optimal tour and its total distance.
How this page computes
The edge list becomes a symmetric distance matrix, with a missing pair refused by name. The subset table stores, for every mask of the non-start nodes and every last node, the cheapest distance and the node it came from.
The table is filled by increasing mask, then the closing edge is added to each possible last node. The tour is rebuilt from the stored predecessors, so the printed route and the printed distance are the same solution.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page visits every node once and returns to the start, and it proves the tour is the shortest one rather than a good guess. On the four-node sample the optimal tour A, D, C, B, A costs 16, while the greedy nearest-neighbour tour costs more.
Held–Karp makes the proof affordable: it solves every subset of nodes exactly, which is 12·2^12 states at the twelve-node ceiling and cannot be extended to a hundred by waiting. Above twelve the page refuses, because a heuristic answer would be a different claim.
How to use Traveling Salesman (TSP) Solver
Give every pair of nodes a direct edge, one per line, and press Run. A missing pair is refused with the pair named, since a tour that has to teleport between two nodes is not a tour of your graph.
The output gives the tour as a node cycle back to the start, its total distance, and how many subsets were examined. Because ties are broken by node order, the same list always gives the same tour.
Held–Karp, and what the subset table proves
For each subset of nodes and each possible last node in that subset, keep the cheapest way to reach that node having visited exactly that subset. A subset of size k is built from subsets of size k − 1 by adding one node, so every partial tour is considered once.
The final answer adds the closing edge back to the start and takes the best last node. Because every subset and every last node were optimised, no tour was skipped, so the printed tour is the shortest — that is what makes the word optimal honest here.
What to Expect
Best for
- The shortest closed tour through up to twelve nodes
- Checking that a greedy tour is not optimal
- A worked example of an exact exponential algorithm
Not ideal for
- More than twelve nodes, where the page refuses rather than guessing
- Open paths that do not return to the start
- Graphs missing a direct edge between some pair
What this tool keeps
- Every weight exactly as typed
What may need cleanup
- Nothing: the tour and its length are optimal
Common errors
- A missing pair is refused with both node names
- More than twelve nodes is refused with the ceiling named
- Fewer than three nodes is refused as too small for a tour
Example use cases
- Find the shortest round trip through four cities
- Compare a greedy tour with the optimal one
- Check a Held–Karp exercise by hand
Sample input
A-B 3, A-C 5, A-D 4, B-C 2, B-D 6, C-D 7
Sample output
optimal tour A -> D -> C -> B -> A with distance 16
Who this is for
- Students meeting NP-hard problems
- Readers checking a route plan
Frequently asked questions
Why only twelve nodes?
The exact method enumerates every subset, so the work doubles with each added node. Twelve nodes is 4096 subsets and finishes instantly; twenty is a million times more work, and a heuristic answer for that size would not be the shortest tour, so the page does not claim one.
Is the tour always unique?
No. Two different tours can have the same length, especially with repeated weights. The page prints the one it finds first in node order, so the printed tour is reproducible.
Can I reverse the tour?
Yes, and it has the same length: every tour and its reverse cost the same because the edges are undirected. The page prints one orientation, not both.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.