TheHeld–Karp algorithm, also called theBellman–Held–Karp algorithm, is adynamic programming algorithm proposed in 1962 independently byBellman^[1] and by Held andKarp^[2] to solve thetraveling salesman problem (TSP), in which the input is adistance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point. It finds the exact solution to this problem, and to several related problems including theHamiltonian cycle problem, inexponential time.

Number the cities${\displaystyle 1,2,\dots ,n}$, with${\displaystyle 1}$ designated arbitrarily as a "starting" city (since the solution to TSP is a Hamiltonian cycle, the choice of starting city doesn't matter). The Held–Karp algorithm begins by calculating, for each set of cities${\displaystyle S\subseteq \{2,\dots ,n\}}$ and every city${\displaystyle e\ne 1}$ not contained in${\displaystyle S}$, the shortest one-way path from${\displaystyle 1}$ to${\displaystyle e}$ that passes through every city in${\displaystyle S}$ in some order (but not through any other cities). Denote this distance${\displaystyle g(S,e)}$, and write${\displaystyle d(u,v)}$ for the length of the direct edge from${\displaystyle u}$ to${\displaystyle v}$. We'll compute values of${\displaystyle g(S,e)}$ starting with the smallest sets${\displaystyle S}$ and finishing with the largest.

When${\displaystyle S}$ has two or fewer elements, then calculating${\displaystyle g(S,e)}$ requires looking at one or two possible shortest paths. For example,${\displaystyle g(\mathrm{\varnothing },e)}$ is simply${\displaystyle d(1,e)}$, and${\displaystyle g(\{2\},3)}$ is just the length of${\displaystyle 1\to 2\to 3}$. Likewise,${\displaystyle g(\{2,3\},4)}$ is the length of either${\displaystyle 1\to 2\to 3\to 4}$ or${\displaystyle 1\to 3\to 2\to 4}$, whichever is shorter.

Once${\displaystyle S}$ contains three or more cities, the number of paths through${\displaystyle S}$ rises quickly, but only a few such paths need to be examined to find the shortest. For instance, if${\displaystyle 1\to 2\to 3\to 4}$ is shorter than${\displaystyle 1\to 3\to 2\to 4}$, then${\displaystyle 1\to 2\to 3\to 4\to 5}$ must be shorter than${\displaystyle 1\to 3\to 2\to 4\to 5}$, and the length of${\displaystyle 1\to 3\to 2\to 4\to 5}$ is not a possible value of${\displaystyle g(\{2,3,4\},5)}$. Similarly, if the shortest path from${\displaystyle 1}$ through${\displaystyle \{2,3,4\}}$ to${\displaystyle 5}$ is${\displaystyle 1\to 4\to 3\to 2\to 5}$, and the shortest path from${\displaystyle 1}$ through${\displaystyle \{2,3,4,5\}}$ to${\displaystyle 6}$ ends with the edge${\displaystyle 5\to 6}$, then the whole path from${\displaystyle 1}$ to${\displaystyle 6}$ must be${\displaystyle 1\to 4\to 3\to 2\to 5\to 6}$, and not any of the other five paths created by visiting${\displaystyle \{2,3,4\}}$ in a different order.

More generally, suppose${\displaystyle S=\{s_1,\dots ,s_k\}}$ is a set of${\displaystyle k}$ cities. For every integer${\displaystyle 1\le i\le k}$, write${\displaystyle S_i=S\setminus \{s_i\}=\{s_1,\dots ,s_{i-1},s_{i+1},\dots ,s_k\}}$ for the set created by removing${\displaystyle s_i}$ from${\displaystyle S}$. Then if the shortest path from${\displaystyle 1}$ through${\displaystyle S}$ to${\displaystyle e}$ has${\displaystyle s_i}$ as its second-to-last city, then removing the final edge from this path must give the shortest path from${\displaystyle 1}$ to${\displaystyle s_i}$ through${\displaystyle S_i}$. This means there are only${\displaystyle k}$ possible shortest paths from${\displaystyle 1}$ to${\displaystyle e}$ through${\displaystyle S}$, one for each possible second-to-last city${\displaystyle s_i}$ with length${\displaystyle g(S_i,s_i)+d(s_i,e)}$, and${\displaystyle g(S,e)=\underset{1\le i\le k}{min}g(S_i,s_i)+d(s_i,e)}$.

This stage of the algorithm finishes when${\displaystyle g(\{2,\dots ,i-1,i+1,\dots ,n\},i)}$ is known for every integer${\displaystyle 2\le i\le n}$, giving the shortest distance from city${\displaystyle 1}$ to city${\displaystyle i}$ that passes through every other city. The much shorter second stage adds these distances to the edge lengths${\displaystyle d(i,1)}$ to give${\displaystyle n-1}$ possible shortest cycles, and then finds the shortest.

The shortest path itself (and not just its length), finally, may be reconstructed by storing alongside${\displaystyle g(S,e)}$ the label of the second-to-last city on the path from${\displaystyle 1}$ to${\displaystyle e}$ through${\displaystyle S}$, raising space requirements by only a constant factor.

The Held–Karp algorithm has exponential time complexity${\displaystyle \mathrm{\Theta }(2^n{n}^2)}$, significantly better than the superexponential performance${\displaystyle \mathrm{\Theta }(n!)}$ of a brute-force algorithm. Held–Karp, however, requires${\displaystyle \mathrm{\Theta }(n{2}^n)}$ space to hold all computed values of the function${\displaystyle g(S,e)}$, while brute force needs only${\displaystyle \mathrm{\Theta }(n^2)}$ space to store the graph itself.

Computing one value of${\displaystyle g(S,e)}$ for a${\displaystyle k}$-element subset${\displaystyle S}$ of${\displaystyle \{2,\dots ,n\}}$ requires finding the shortest of${\displaystyle k}$ possible paths, each found by adding a known value of${\displaystyle g}$ and an edge length from the original graph; that is, it requires time proportional to${\displaystyle k}$. There are$(\genfrac{}{}{0ex}{}{n-1}{k})$${\displaystyle k}$-element subsets of${\displaystyle \{2,\dots ,n\}}$; and each subset gives${\displaystyle n-k-1}$ possible values of${\displaystyle e}$. Computing all values of${\displaystyle g(S,e)}$ where${\displaystyle |S|=k}$ thus requires time$k(n-k-1)(\genfrac{}{}{0ex}{}{n-1}{k})=(n-1)(n-2)(\genfrac{}{}{0ex}{}{n-3}{k-1})$, for a total time across all subset sizes$(n-1)(n-2)\sum _{k=1}^{n-2}(\genfrac{}{}{0ex}{}{n-3}{k-1})=(n-1)(n-2)2^{n-3}=\mathrm{\Theta }(n^2{2}^n)$. The second stage of the algorithm, finding a complete cycle from${\displaystyle n-1}$ candidates, takes${\displaystyle \mathrm{\Theta }(n)}$ time and does not affect asymptotic performance.

Forundirected graphs, the algorithm can be stopped early after the$k=\lfloor \frac{n-1}{2}\rfloor$ step, and finding the minimum$g(S,e)+g(S^c\setminus \{1,e\},e)$ for every$\{(S,e):|S|=\lfloor \frac{n-1}{2}\rfloor ,e\in S^c\setminus \{1\}\}$, where$S^c$ is thecomplement set of$S$. This is analogous to abidirectional search starting at$1$ and meeting at midpoint$e$. However, this is a constant factor improvement and does not affect asymptotic performance.

Storing all values of${\displaystyle g(S,e)}$ for subsets of size${\displaystyle k}$ requires keeping$(n-k-1)(\genfrac{}{}{0ex}{}{n-1}{k})=(n-1)(\genfrac{}{}{0ex}{}{n-2}{k})$ values. A complete table of values of${\displaystyle g(S,e)}$ thus requires space$\sum _{k=0}^{n-2}(n-1)(\genfrac{}{}{0ex}{}{n-2}{k})=(n-1)2^n=\mathrm{\Theta }(n{2}^n)$. This assumes that$n$ is sufficiently small enough such that$S$ can be stored as abitmask of constant multiple ofmachine words, rather than an explicit k-tuple.

If only the length of the shortest cycle is needed, not the cycle itself, thenspace complexity can be improved somewhat by noting that calculating${\displaystyle g(S,e)}$ for a${\displaystyle S}$ of size${\displaystyle k}$ requires only values of${\displaystyle g}$ for subsets of size${\displaystyle k-1}$. Keeping only the$(n-1)\left[(\genfrac{}{}{0ex}{}{n-2}{k-1})+(\genfrac{}{}{0ex}{}{n-2}{k})\right]$ values of${\displaystyle g(S,e)}$ where${\displaystyle S}$ has size either${\displaystyle k-1}$ or${\displaystyle k}$ reduces the algorithm's maximum space requirements, attained when$k=\lfloor \frac{n}{2}\rfloor$, to${\displaystyle \mathrm{\Theta }(\sqrt{n}{2}^n)}$.

Source:^[3]

function algorithm TSP (G, n)isfor k := 2 to ndo        g({k}, k) := d(1, k)end forfor s := 2to n−1dofor all S ⊆ {2, ..., n}, |S| = sdofor all k ∈ Sdo                g(S, k) := minm≠k,m∈S [g(S\{k}, m) + d(m, k)]end forend forend for    opt := mink≠1 [g({2, 3, ..., n}, k) + d(k, 1)]return (opt)end function

• Dynamic programming
• Travelling salesman problem

• Articles with short description
• Short description matches Wikidata