Кристофајдсов алгоритам
Циљ Кристофајдсовог хеуристичког алгоритма (названог по Никосу Кристофајдсу) јесте да се нађе решење за случајеве "проблем трговачког путника" , где тежине грана задовољавају неједнакост троугла.
Нека  буде пример ПТП (проблем трговачког путника), односно  је комплетан граф скупом  чворова са функцијом тежине  додељујући ненегативну целобронју вредност као тежину за сваку грану .

Алгоритам 
Псеудокод:
 Направите минимално разапињуће стабло МРС  од .
 Нека  буде скуп чворова непарног степена у  и тражимо савршено подударање  са минималном тежином комплетног графа са чворовима из .
 Комбинују се гране из  и  да формирају мултиграф .
 Формира се Ојлеров циклус у  (H је Oјлеров, јер је повезан само са чворовима парног степена) .
 Направи се циклус пронађен у претходном кораку , Хамилтонов, прескачући већ посећене чворове (Shortcutting).

Апроксимативни однос 

Трошкови решења које производи алгоритма су 3/2 од оптимума.

Доказ је следећи:

Нека је  означавају скуп грана оптималног решење ПТП за . Зато што је  повезан, он садржи неко разапињуће стабло  и тада .

Даље нека  означава скуп грана оптималног решења ПТП за комплетан граф преко чворова из .

Зато што су тежине грана троугаоне (посета више чворова не може да смањи укупне трошкове), знамо да
.

Показали смо да постоји савршено поклапање чворова  и тежина испод  и зато имамо исту горњу границу за  (јер је  савршено поклапање са минималним трошковима).

Зато што  мора да садржи паран број чворова, савршено подударање постоји. Нека
 буде (једини) Ојлеров пут у .

Јасно је да се
 и
 савршено поклапају , па је тежина барем једног од њих је
мања или једнака .

Тако је  и из неједнакости троугла следи да је алгоритам 3/2-апроксимативан.

Литература 
 NIST Christofides Algorithm Definition
 Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

Графовски алгоритми
Циљ Кристофајдсовог хеуристичког алгоритма ( названог по Никосу Кристофајдсу ) јесте да се нађе решење за случајеве " проблем трговачког путника " , где тежине грана задовољавају неједнакост троугла . Нека буде пример ПТП ( проблем трговачког путника ) , односно је комплетан граф скупом чворова са функцијом тежине додељујући ненегативну целобронју вредност као тежину за сваку грану \ . Алгоритам Псеудокод : Направите минимално разапињуће стабло МРС од \ . Нека буде скуп чворова непарног степена у и тражимо савршено подударање са минималном тежином комплетног графа са чворовима из \ . Комбинују се гране из и да формирају мултиграф \ . Формира се Ојлеров циклус у ( H је Oјлеров , јер је повезан само са чворовима парног степена ) \ . Направи се циклус пронађен у претходном кораку , Хамилтонов , прескачући већ посећене чворове ( Shortcutting ) . Апроксимативни однос Трошкови решења које производи алгоритма су2 од оптимума . Доказ је следећи : Нека је означавају скуп грана оптималног решење ПТП за \ . Зато што је повезан , он садржи неко разапињуће стабло и тада \ . Даље нека означава скуп грана оптималног решења ПТП за комплетан граф преко чворова из \ . Зато што су тежине грана троугаоне ( посета више чворова не може да смањи укупне трошкове ) , знамо да . Показали смо да постоји савршено поклапање чворова и тежина испод и зато имамо исту горњу границу за ( јер је савршено поклапање са минималним трошковима ) . Зато што мора да садржи паран број чворова , савршено подударање постоји . Нека буде ( једини ) Ојлеров пут у \ . Јасно је да се и савршено поклапају , па је тежина барем једног од њих је мања или једнака \ . Тако је и из неједнакости троугла следи да је алгоритам2-апроксимативан . Литература NIST Christofides Algorithm Definition Nicos Christofides , Worst-case analysis of a new heuristic for the travelling salesman problem , Report Graduate School of Industrial Administration , CMU , Графовски алгоритми