Held–Karp algorithm

Number the cities ${\displaystyle 1,2,\ldots ,n}$, with ${\displaystyle 1}$ designated arbitrarily as a "starting" city (since the solution to TSP is a 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,\ldots ,n\}}$ and every city ${\displaystyle e\neq 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(\emptyset ,e)}$ is simply ${\displaystyle d(1,e)}$, and ${\displaystyle g(\{2\},3)}$ is just the length of ${\displaystyle 1\rightarrow 2\rightarrow 3}$. Likewise, ${\displaystyle g(\{2,3\},4)}$ is the length of either ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}$ or ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 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\rightarrow 2\rightarrow 3\rightarrow 4}$ is shorter than ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$, then ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5}$ must be shorter than ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$, and the length of ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 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\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5}$, and the shortest path from ${\displaystyle 1}$ through ${\displaystyle \{2,3,4,5\}}$ to ${\displaystyle 6}$ ends with the edge ${\displaystyle 5\rightarrow 6}$, then the whole path from ${\displaystyle 1}$ to ${\displaystyle 6}$ must be ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 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},\ldots ,s_{k}\}}$ is a set of ${\displaystyle k}$ cities. For every integer ${\displaystyle 1\leq i\leq k}$, write ${\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,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)=\min _{1\leq i\leq k}g(S_{i},s_{i})+d(s_{i},e)}$.

This stage of the algorithm finishes when ${\displaystyle g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)}$ is known for every integer ${\displaystyle 2\leq i\leq 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 \Theta (2^{n}n^{2})}$, significantly better than the superexponential performance ${\displaystyle \Theta (n!)}$ of a brute-force algorithm. Held–Karp, however, requires ${\displaystyle \Theta (n2^{n})}$ space to hold all computed values of the function ${\displaystyle g(S,e)}$, while brute force needs only ${\displaystyle \Theta (n^{2})}$ space to store the graph itself.

Distance matrix:

${\displaystyle C={\begin{pmatrix}0&2&9&10\\1&0&6&4\\15&7&0&8\\6&3&12&0\end{pmatrix}}}$

Functions description:

• g(x, S) - starting from 1, path min cost ends at vertex x, passing vertices in set S exactly once
• c_xy - edge cost ends at x from y
• p(x, S) - the second-to-last vertex to x from set S. Used for constructing the TSP path back at the end.

k = 0, null set:

Set ∅:

       g(2, ∅) = c21 = 1 
       g(3, ∅) = c31 = 15
       g(4, ∅) = c41 = 6

k = 1, consider sets of 1 element:

Set {2}:

       g(3,{2}) = c32 + g(2, ∅ ) = c32 + c21 = 7 + 1 = 8       p(3,{2}) = 2
       g(4,{2}) = c42 + g(2, ∅ ) = c42 + c21 = 3 + 1 = 4       p(4,{2}) = 2

Set {3}:

       g(2,{3}) = c23 + g(3, ∅ ) = c23 + c31 = 6 + 15 = 21     p(2,{3}) = 3
       g(4,{3}) = c43 + g(3, ∅ ) = c43 + c31 = 12 + 15 = 27    p(4,{3}) = 3

Set {4}:

       g(2,{4}) = c24 + g(4, ∅ ) = c24 + c41 = 4 + 6 = 10      p(2,{4}) = 4
       g(3,{4}) = c34 + g(4, ∅ ) = c34 + c41 = 8 + 6 = 14      p(3,{4}) = 4

k = 2, consider sets of 2 elements:

Set {2,3}:

         g(4,{2,3}) = min {c42 + g(2,{3}), c43 + g(3,{2})} = min {3+21, 12+8}= min {24, 20}= 20
         p(4,{2,3}) = 3

Set {2,4}:

         g(3,{2,4}) = min {c32 + g(2,{4}), c34 + g(4,{2})} = min {7+10, 8+4}= min {17, 12} = 12
         p(3,{2,4}) = 4

Set {3,4}:

          g(2,{3,4}) = min {c23 + g(3,{4}), c24 + g(4,{3})} = min {6+14, 4+27}= min {20, 31}= 20
          p(2,{3,4}) = 3

Length of an optimal tour:

 f = g(1,{2,3,4}) = min { c12 + g(2,{3,4}), c13 + g(3,{2,4}), c14 + g(4,{2,3}) }
                  = min {2 + 20, 9 + 12, 10 + 20} = min {22, 21, 30} = 21

Predecessor of node 1: p(1,{2,3,4}) = 3

Predecessor of node 3: p(3, {2,4}) = 4

Predecessor of node 4: p(4, {2}) = 2

Predecessor of node 2: p(2, {}) = 1

Hence, an optimal TSP tour is given by 1 → 2→ 4 → 3→ 1.

function algorithm TSP (G, n) is
    for k := 2 to n do
        g({k}, k) := d(1, k)
    end for

    for s := 2 to n−1 do
        for all S ⊆ {2, ..., n}, |S| = s do
            for all k ∈ S do
                g(S, k) := minm≠k,m∈S [g(S\{k}, m) + d(m, k)]
            end for
        end for
    end for

    opt := mink≠1 [g({2, 3, ..., n}, k) + d(k, 1)]
    return (opt)
end function