A route that visits every location once cannot usually be built by repeatedly taking its cheapest outgoing edge. That choice may leave an unvisited location inaccessible, or may make the eventual return expensive. Trying every visiting order does solve the problem, but it repeats many subproblems: two different prefixes can leave exactly the same choices for the future.
Dynamic programming becomes useful when we can state precisely what makes two prefixes interchangeable. Here it is their set of visited vertices and their current endpoint. The internal order of the prefix affects its cost, but no longer affects which vertices remain available or which edge can be taken next. We can retain the cheapest prefix with each such state.
This method is exact and still exponential. Its purpose is to exploit repeated states when the number of vertices is small, rather than turn arbitrary large tour problems into easy computations.
Specify the route before defining its state
Vertices are , with . For distinct vertices , a directed edge either exists with integer cost or is absent. Costs can be zero or negative. There is no symmetry or triangle-inequality assumption.
A simple path starting at 0 lists distinct vertices, beginning with 0, and uses an existing edge between consecutive vertices. For , a Hamiltonian tour is such a path visiting all vertices, followed by an existing edge back to 0. Thus 0 occurs once at the start and once at the end; each other vertex occurs exactly once. We minimize the sum of all traversed edge costs. Fixing the starting vertex as 0 loses no cycle: any such cycle can be written beginning at 0.
For , we use the explicit convention that the zero-edge tour has cost zero and witness [0]. No self-loop is required or counted, even if the diagonal matrix entry is negative. Diagonal entries are otherwise irrelevant because vertices cannot be revisited inside the path.
Definition 14.1.1
(The exact visited-set and endpoint state)
For containing 0 and , let be the minimum cost of a simple path from 0 to whose visited set is exactly . If no such path exists, write .
The one-vertex path gives . All states ending at 0 with are unreachable: a simple path starting at 0 cannot return to 0 internally. States with or are invalid and are never needed.
The word “exactly” prevents a cheaper path through additional vertices from being used as if those vertices were still available. The endpoint is also necessary: two paths visiting the same set can end at different vertices, and hence face different next-edge costs or missing next edges.
Derive the recurrence by removing the final edge
Theorem 14.1.2
(Final-edge recurrence)
Let contain , and let with . A path qualifying for reaches from some along an existing edge , and
Here the minimum of no candidates is .
Proof
(Remove the final edge, then append it back)
Take any qualifying path for . Remove its final edge . Because all listed vertices are distinct, the remaining path visits exactly and ends at . Its cost is at least , so the complete path costs at least one recurrence candidate. Taking the cheapest qualifying path gives a lower bound by the right-hand minimum.
Conversely, take a reachable candidate on the right and an optimal prefix realizing it. Vertex is not in the prefix's visited set. Appending the existing edge therefore creates a simple path with exactly the required visited set, and its cost equals that candidate. The cheapest candidate is achievable, giving the opposite inequality. If there is no candidate, no qualifying path could have a final edge, so the state is unreachable.
Proof X-ray
Where distinctness and exactness enter
Both inequalities rest on one property of a simple path: its vertices are distinct. In the lower bound it guarantees that deleting the last edge leaves a path whose visited set is exactly . In the upper bound it shows that is not in the prefix's visited set, so appending gives a simple path whose visited set is exactly . The non-routine point is that the two inequalities use different prefixes: an optimal path for in one direction, and a separately chosen optimal prefix for each candidate in the other. Nowhere is the sign of a cost used, only that cost adds along a path. The argument closes by induction on : every term on the right concerns a set with one fewer vertex, and the base is . Without distinctness, deleting the last edge could leave a prefix that still contains , and the recurrence would no longer describe visited sets.
An unreachable prefix supplies no candidate, and the minimum of no candidates is . Every dependency uses a set smaller by one vertex, so cardinality gives an acyclic computation order.
There are only finitely many simple paths in a finite graph, so every reachable minimum is achieved, even when some costs are negative. We do not repeatedly relax cycles: each transition adds a previously unvisited vertex. Negative cycles cannot make this finite simple-route optimization unbounded below.
Equivalently, a forward implementation starts from a reachable and appends any with an existing edge. It improves using . These are the same transitions with their direction of explanation reversed.
Why discarding other prefixes is safe
Lemma 14.1.3
(Equivalent prefixes can be interchanged)
Let two simple paths from visit exactly the same set and end at the same vertex . If a sequence of vertices outside , followed by the return to , completes the first path to a Hamiltonian tour, then the same sequence completes the second path, and the two tours differ in cost by exactly the difference of the two prefix costs.
Proof
(The continuation sees only the set and the endpoint)
Any future sequence completing one prefix must use vertices outside , then return to 0. The other prefix has the same unused vertices and the same first departure vertex , so the same future sequence is legal for it and has the same added cost.
Replacing a more expensive prefix by a cheapest one therefore cannot spoil a completion or increase its total cost. This argument does not require nonnegative costs. It does require that feasibility and cost of the continuation depend only on the visited set, current endpoint and future edges. Additional constraints depending on earlier order may require a richer state.
Counterexample mode
The cheapest path to an endpoint can have the wrong visited set
Use three vertices with edges of cost 1 and , , , of cost zero. There is no edge and no other edge. The only Hamiltonian tour is , with cost 1.
The cheapest simple path from 0 to endpoint 1 is instead , with cost zero. Reusing it as a prefix that has visited only would allow the false route of cost zero, which repeats vertex 2. A single cheapest value per endpoint loses essential information. The states and must remain distinct.
Closing a path is a separate requirement
Theorem 14.1.4
(Optimal tour from the full-set states)
Let . A Hamiltonian tour exists exactly when some has finite and an edge . In that case the minimum tour cost is
Proof
(A tour is a full-set path plus a closing edge)
Every Hamiltonian tour is a simple path from visiting exactly and ending at some , followed by an existing edge ; conversely, every such pair is a tour. Its cost is the path cost plus . For fixed the second term is constant, so the cheapest tour with last vertex uses a path of cost . Minimizing over gives the formula, and if no qualifies there is no tour.
A finite guarantees a Hamiltonian path, not a tour: the closing edge may be absent. If there is no candidate, report that no tour exists rather than returning an arbitrary large number.
Worked example 14.1.5
(Compare complete paths only after adding their closing costs)
Consider this directed cost matrix, with a dash for an absent or unused diagonal entry:
| From / to | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | — | 2 | 9 | 8 |
| 1 | 6 | — | 3 | 7 |
| 2 | 4 | 5 | — | -2 |
| 3 | 1 | 6 | 4 | — |
For , the path ending at 2 is with cost , while the one ending at 1 is with cost . Extending to endpoint 3 compares with , so .
| Full-set endpoint | Closing cost | Tour candidate | |
|---|---|---|---|
| 1 | 13 | 6 | 19 |
| 2 | 13 | 4 | 17 |
| 3 | 3 | 1 | 4 |
The optimum is , with cost . For example, the full-set path ending at 1 of cost 13 is ; it is not a cost-13 tour, because returning to 0 adds 6.
Common mistake
(Minimizing the path cost instead of the tour cost)
Take edges , , and of cost , and of cost and of cost . The cheapest full-set path is with cost , but closing it costs , so that tour costs . The path costs and closes for , giving a tour of cost . Choosing the endpoint by alone returns instead of the optimum ; the closing cost must be added before comparing endpoints.
Encode a set without encoding its visiting order
Use an integer mask whose bit is one exactly when . Then membership tests use mask & (1 << i), adjoining a previously absent vertex uses mask | (1 << i), and the full set has mask (1 << n) - 1. Bit positions name vertices; the written binary digits do not record visiting order.
Every forward transition sets a zero bit, so the new mask is numerically larger than the old mask. Iterating masks in increasing order is consequently a valid topological order, even though sets of a fixed cardinality are not contiguous in this order. A state receives every possible improvement before it is used for extensions.
When a transition strictly improves a state, store the previous endpoint in a parent table for that exact state. The previous mask is determined by removing the new endpoint. During reconstruction, keep both the current mask and endpoint: the same endpoint can have different predecessors in different subset states. Retaining any one minimum-cost predecessor is enough; the output contract does not demand a lexicographically smallest tour.
Executable implementation and its contract
Input is a nonempty square matrix of integers or None, where None means that an edge is absent. An integer zero is a real zero-cost edge. Entries on the diagonal are ignored. The function returns (cost, witness) for an optimal tour, or None if no tour exists. For more than one vertex the witness repeats 0 at the end; the one-vertex convention returns (0, [0]). The matrix is read without mutation.
def minimum_hamiltonian_tour(weights):
n = len(weights)
if n == 0 or any(len(row) != n for row in weights):
raise ValueError("a nonempty square matrix is required")
if n == 1:
return 0, [0]
limit = 1 << n
dp = [[None] * n for _ in range(limit)]
parent = [[None] * n for _ in range(limit)]
dp[1][0] = 0
for mask in range(1, limit):
if not mask & 1:
continue
for last in range(n):
cost = dp[mask][last]
if cost is None:
continue
for nxt in range(1, n):
if mask & (1 << nxt):
continue
edge = weights[last][nxt]
if edge is None:
continue
new_mask = mask | (1 << nxt)
candidate = cost + edge
old = dp[new_mask][nxt]
if old is None or candidate < old:
dp[new_mask][nxt] = candidate
parent[new_mask][nxt] = last
full = limit - 1
best = None
endpoint = None
for last in range(1, n):
cost = dp[full][last]
closing = weights[last][0]
if cost is None or closing is None:
continue
candidate = cost + closing
if best is None or candidate < best:
best = candidate
endpoint = last
if endpoint is None:
return None
path = []
mask = full
last = endpoint
while mask != 1:
path.append(last)
previous = parent[mask][last]
mask ^= 1 << last
last = previous
path.append(0)
path.reverse()
path.append(0)
return best, path
The code assumes the promised integer-or-None entries and checks matrix shape. It compares absence with is None, so zero and negative costs remain valid. Separate rows are allocated for every mask. Each recorded parent belongs to a reachable transition from a smaller mask; reconstruction therefore removes one visited nonzero vertex per step and reaches the base state. No parent of the base state is needed.
Worked example 14.1.6
(The parent chain also records which set each predecessor used)
For the four-vertex optimum, write masks with bit 0 on the right. The parent chain is
Reconstruction first collects backwards. Reversing gives ; append the closing vertex 0 to obtain . Each removed bit certifies that a vertex is removed from the visited set exactly once. The cost is checked against the original directed edges, including the closing edge.
Worked example 14.1.7
(The smallest tours: two vertices and one vertex)
Take with and . The code sets dp[1][0]=0. From mask it extends to vertex , so dp[3][1]=0+5=5 and parent[3][1]=0. For the full mask the only endpoint is , with closing cost , so best . Reconstruction appends , moves to the parent , and stops at mask ; appending , reversing and appending the closing gives the witness . If the edge were absent, the closing cost would be None, no endpoint would qualify and the function would return None: a full-set path exists but no tour does. For the function returns without using the diagonal entry.
Common mistake
(Testing for a missing edge by truthiness)
Writing if not edge: continue treats the cost as an absent edge. For two vertices with and the edge would be skipped, no tour would be found, and the function would return None, although the tour of cost exists. Absence must be tested with is None, which keeps zero and negative costs valid.
Count the states and respect the problem boundary
Proposition 14.1.8
(Cost of the subset dynamic program)
For vertices, the implementation performs arithmetic operations, stores table cells and reconstructs a witness in time.
Proof
(Count states, then transitions)
There are masks and endpoints per mask, hence at most positions in each table, including invalid or unreachable positions allocated by this simple implementation. Each reachable state considers at most next vertices with a constant number of operations, which gives . The final minimization over endpoints costs . Reconstruction removes one bit per step, so it takes at most steps.
Both tables are exponential, so even moderately increasing can make this method impractical.
These bounds treat mask operations and integer cost arithmetic as unit operations. They are not bit-complexity bounds for arbitrarily large or costs: masks use bits, and exact accumulated costs also need enough bits. Python integers avoid fixed-width overflow, but do not make large arithmetic free.
Counterexample mode
Replacing missing edges by shortest-path distances changes the question
Suppose the only arcs are , , , , each of cost 1. There is no Hamiltonian tour on the original graph: from 0 a tour must first visit 1, then 2, but there is no edge .
Replacing every pair by its shortest-path distance creates a complete distance matrix. A tour in that matrix has cost , but its final distance expands to . The resulting original-graph walk repeats vertex 1. A closed walk visiting every vertex at least once is a different optimization problem from a Hamiltonian tour in the supplied graph.
Subset dynamic programming is valuable beyond this particular objective. The reusable reasoning is to identify the information that fixes all future choices, prove that cheaper equivalent prefixes can replace more expensive ones, and order transitions by a quantity that strictly increases. The visited set alone, the endpoint alone, or an unexplained bitmask is not a correctness proof.
Exercises with complete solutions
Quick check
(With four vertices and bit 0 on the right, encode as a mask. Can the mask tell whether a path visited before ? Is endpoint valid for this state?)
Add the powers of two for the members.
Solution · Answer
The mask is , written 1101. Both visiting orders would give the same mask, so it does not encode their order. Endpoint 1 is invalid because . A reachable state also needs an actual path using the available edges; a syntactically valid mask and endpoint do not guarantee reachability.
Quick check
(In the four-vertex matrix, compute and , then use both candidates to compute .)
Append vertex to each of the two paths.
Solution · Answer
The two smaller-state paths are with cost and with cost . Appending vertex 3 gives candidates and . Their minimum is . Adding the final edge then gives a tour of cost .
Quick check
(For two vertices, the only off-diagonal costs are and . What is returned? What changes if the return edge is absent? For one vertex, what if its diagonal entry is ?)
An absent edge is None, not zero.
Solution · Answer
With both arcs, the answer is cost and witness . A zero-cost edge must not be mistaken for absence. Removing leaves a full-set path but no tour, so the function returns None. For one vertex the explicitly chosen zero-edge convention returns , ignoring the diagonal .
Quick check
(In the three-vertex endpoint counterexample, why is not an admissible cost-zero answer? Which state retains the prefix needed for the genuine optimum?)
Check which vertex the route visits twice.
Solution · Answer
The route visits vertex 2 twice before closing at 0, so it is not Hamiltonian. The needed prefix is , represented by . It can legally append the still-unvisited vertex 2 and return to 0 for total cost 1. The cheaper state ending at 1 has visited set , so it cannot append 2 again and has no closing edge to 0.
Quick check
(Reconstruct the tour from the parent states , , , . Why store parents by both mask and endpoint instead of by endpoint alone?)
Read the endpoints backwards, then reverse them.
Solution · Answer
Read endpoints backwards as , reverse them, and append the final 0 to get . Each step removes the current endpoint's bit. The same endpoint may be reached optimally through different vertices for different visited sets; one parent per endpoint could splice unrelated states together and repeat or omit vertices. A parent for each pair preserves the recurrence that produced the stored cost.
Quick check
(Why is the bound rather than polynomial? Why are negative edges allowed here even though a greedy shortest-path algorithm may require nonnegative edges?)
Count the states, then ask what every transition does to the visited set.
Solution · Answer
There are up to subsets and endpoints per subset, with at most extensions per state, giving arithmetic operations. The exponential factor remains; this is not a polynomial-time guarantee. Negative edges do not break the recurrence because every transition strictly enlarges the visited set. The dependency graph is acyclic and the finite set of simple paths has an achieved minimum. Correctness comes from exact state decomposition, not from greedily finalizing the smallest current distance.