Traveling Salesman (TSP) Solver screenshot

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.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Provably optimal

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.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.