Stay organized with collections
Save and categorize content based on your preferences.
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.
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe Christofides algorithm provides an approximate solution to the Traveling Salesman Problem, guaranteeing a solution within 3/2 of the optimum.\u003c/p\u003e\n"],["\u003cp\u003eThe algorithm's complexity depends heavily on the matching algorithm used, ranging from O(n² log(n)) with minimal matching to at least O(n³) or O(nm log(n)) with other perfect matching algorithms.\u003c/p\u003e\n"],["\u003cp\u003eChristofidesPathSolver is the class used to implement the Christofides algorithm for finding approximate solutions.\u003c/p\u003e\n"]]],["ChristofidesPathSolver utilizes the Christofides algorithm to approximate solutions for the Traveling Salesman Problem, ensuring results within 3/2 of the optimum when using minimum weight perfect matching. The algorithm's complexity is dictated by the matching phase, which is O(n^2 * log(n)) with minimal matching or at least O(n^3) or O(nmlog(n)) otherwise, with n representing nodes and m edges. The Christofides algorithm can be found at the provided wikipedia link.\n"],null,["# christofides\n\nC++ Reference: christofides\n===========================\n\n\nNote: This documentation is automatically generated.\nChristofidesPathSolver computes an approximate solution to the Traveling Salesman Problen using the Christofides algorithm (c.f. \u003chttps://en.wikipedia.org/wiki/Christofides_algorithm\u003e). 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. \n\n| Classes ------- ||\n|---------------------------------------------------------------------------------------------|---|\n| [ChristofidesPathSolver](/optimization/reference/graph/christofides/ChristofidesPathSolver) |"]]
