Stay organized with collections Save and categorize content based on your preferences.

C++ Reference: class ChristofidesPathSolver

Note: This documentation is automatically generated.


Arguments: NodeIndex num_nodes, CostFunction costs


Return type: void

Arguments: MatchingAlgorithm matching

Sets the matching algorithm to use. A minimum weight perfect matching (MINIMUM_WEIGHT_MATCHING) guarantees the 3/2 upper bound to the optimal solution. A minimal weight perfect matching (MINIMAL_WEIGHT_MATCHING) finds a locally minimal weight matching which does not offer any bound guarantee but, as of 1/2017, is orders of magnitude faster than the minimum matching. By default, MINIMAL_WEIGHT_MATCHING is selected. TODO(user): Change the default when minimum matching gets faster.


Return type: bool

Runs the Christofides algorithm. Returns true if a solution was found, false otherwise.


Return type: CostType

Returns the cost of the approximate TSP tour.


Return type: std::vector<NodeIndex>

Returns the approximate TSP tour.