クリストフィードのアルゴリズム
G = (V,w)について巡回セールスマン問題を考える。頂点集合をV、その完全グラフをGとし、Gに含まれる全ての辺に対し定義される非負の重み集合をwとする。三角不等式より任意の3つの点u, v, xに対し、w(uv) + w(vx) ≥ w(ux)が成立する。
以下に擬似コードを示す。
Gの最小全域木Tを構築する。
Tに含まれる奇数次の頂点集合をOとする。このとき、握手補題(英語版)よりOは偶数個の頂点を持つ。
Oに含まれる頂点によって与えられる誘導部分グラフにおいて最適マッチングMを探索する。
MとTの辺を統合し、すべての頂点が偶数次となる多重グラフHを構築する。
H内部でオイラー閉路を構成する。
構成したオイラー閉路において、既に訪れた点を飛ばしながら辿る(近道)ことにより、ハミルトン閉路を形成する。