Thuật toán Christofides (đặt tên theo Nicos Christofides) là một thuật toán xấp xỉ cho bài toán người bán hàng trong đó trọng số các cạnh thỏa mãn bất đẳng thức tam giác.Đặt G = ( V , w ) {\displaystyle G=(V,w)} là một trường hợp của bài toán người bán hàng trong đó G {\displaystyle G} là đồ thị đầy đủ với tập hợp đỉnh V {\displaystyle V} và trọng số không âm w {\displaystyle w} cho tất cả các cạnh của G {\displaystyle G} .Các bước của thuật toán là như sau:
Bước 1: Tìm một cây bao trùm nhỏ nhất T {\displaystyle T} của G {\displaystyle G} .
Bước 2: Đặt O {\displaystyle O} là tập hợp các đỉnh có bậc lẻ trong T {\displaystyle T} và tìm một cặp ghép đầy đủ M {\displaystyle M} của các đỉnh trong O {\displaystyle O} với tổng trọng số nhỏ nhất.
Bước 3: Hợp các cạnh của M {\displaystyle M} và T {\displaystyle T} thành một đa đồ thị H {\displaystyle H} .
Bước 4: Tìm một chu trình Euler trên H {\displaystyle H} (H có chu trình Euler do nó liên thông và tất cả các đỉnh đều có bậc chẵn).
Bước 5: Biến đổi chu trình trên thành một chu trình Hamilton bằng cách duyệt qua chu trình từ đầu đến cuối và bỏ qua những đỉnh đã thăm trong quá trình duyệt.