# C++ Reference: christofides

Note: This documentation is automatically generated.

ChristofidesPathSolver computes an approximate solution to the Traveling Salesman Problen using the Christofides algorithm (c.f. https://en.wikipedia.org/wiki/Christofides_algorithm). Note that the algorithm guarantees finding a solution within 3/2 of the optimum when using minimum weight perfect matching in the matching phase. The complexity of the algorithm is dominated by the complexity of the matching algorithm: O(n^2 * log(n)) if minimal matching is used, or at least O(n^3) or O(nmlog(n)) otherwise, depending on the implementation of the perfect matching algorithm used, where n is the number of nodes and m is the number of edges of the subgraph induced by odd-degree nodes of the minimum spanning tree.

## Classes

ChristofidesPathSolver
[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]