El algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por su acrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular.
Fue desarrollado en 1976 por Nicos Christofides, profesor del Imperial College London.
que asocia un peso o valor real positivo a cada arista del grafo
La prueba es la siguiente:[3] Sea A el conjunto de aristas de la solución óptima del TSP para G. Como (V,A) es conexo, contendrá varios árboles recubridores T, y por tanto, w(A) ≥ w(T).
Como los pesos asociados a las aristas son "triangulares" (visitar más nodos no reduce, en ningún caso, el coste total), se tiene que w(A) ≥ w(B).