Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class HamiltonianPathSolver
Note: This documentation is automatically generated.
| Method |
BestHamiltonianPathEndNode | Return type: int Returns the end-node that yields the shortest Hamiltonian path of
all shortest Hamiltonian path from 0 to end-node (end-node != 0).
|
ChangeCostMatrix | Return type: void Arguments: CostFunction cost Replaces the cost matrix while avoiding re-allocating memory.
|
ChangeCostMatrix | Return type: void Arguments: int num_nodes, CostFunction cost |
HamiltonianCost | Return type: CostType Arguments: int end_node Returns the cost of the Hamiltonian path from 0 to end_node.
|
HamiltonianPath | Return type: std::vector<int> Arguments: int end_node Returns the shortest Hamiltonian path from 0 to end_node.
|
HamiltonianPath | Return type: void Arguments: std::vector<PathNodeIndex>* path Deprecated API. Stores HamiltonianPath(BestHamiltonianPathEndNode()) into
*path.
|
HamiltonianPathSolver | Return type: explicit Arguments: CostFunction cost |
HamiltonianPathSolver | Arguments: int num_nodes, CostFunction cost |
IsRobust | Return type: bool Returns true if there won't be precision issues.
This is always true for integers, but not for floating-point types.
|
TravelingSalesmanCost | Return type: CostType Returns the cost of the TSP tour.
|
TravelingSalesmanPath | Return type: std::vector<int> Returns the TSP tour in the vector pointed to by the argument.
|
TravelingSalesmanPath | Return type: void Arguments: std::vector<PathNodeIndex>* path Deprecated API.
|
VerifiesTriangleInequality | Return type: bool Returns true if the cost matrix verifies the triangle inequality.
|
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 \u003ccode\u003eHamiltonianPathSolver\u003c/code\u003e class in C++ helps find the shortest Hamiltonian path or Traveling Salesman Problem (TSP) tour in a graph.\u003c/p\u003e\n"],["\u003cp\u003eIt provides methods to calculate and retrieve the path, cost, and the best end-node for the path.\u003c/p\u003e\n"],["\u003cp\u003eYou can modify the cost matrix of the graph using \u003ccode\u003eChangeCostMatrix\u003c/code\u003e.\u003c/p\u003e\n"],["\u003cp\u003eThe class offers functions to check for robustness (\u003ccode\u003eIsRobust\u003c/code\u003e) and triangle inequality (\u003ccode\u003eVerifiesTriangleInequality\u003c/code\u003e) within the cost matrix.\u003c/p\u003e\n"],["\u003cp\u003eDeprecated APIs exist for retrieving the Hamiltonian path and TSP tour; use the updated methods with return types of \u003ccode\u003estd::vector<int>\u003c/code\u003e instead.\u003c/p\u003e\n"]]],["The `HamiltonianPathSolver` class calculates the shortest Hamiltonian path and Traveling Salesman Problem (TSP) solutions. It can change the cost matrix via `ChangeCostMatrix`. The solver returns the end node with the shortest Hamiltonian path from 0 using `BestHamiltonianPathEndNode`. `HamiltonianCost` gets the cost from 0 to an end node and `HamiltonianPath` provides the actual shortest path. It also determines `TravelingSalesmanCost` and `TravelingSalesmanPath` for the TSP tour. Finally, `IsRobust` and `VerifiesTriangleInequality` provide information about the cost matrix.\n"],null,["# HamiltonianPathSolver\n\nC++ Reference: class HamiltonianPathSolver\n==========================================\n\n\nNote: This documentation is automatically generated.\n\n| Method ||\n|--------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`BestHamiltonianPathEndNode`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L494) | Return type: `int ` Returns the end-node that yields the shortest Hamiltonian path of all shortest Hamiltonian path from 0 to end-node (end-node != 0). |\n| [`ChangeCostMatrix`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L483) | Return type: `void ` Arguments: `CostFunction cost` Replaces the cost matrix while avoiding re-allocating memory. |\n| [`ChangeCostMatrix`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L484) | Return type: `void ` Arguments: `int num_nodes, CostFunction cost` \u003cbr /\u003e |\n| [`HamiltonianCost`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L487) | Return type: `CostType ` Arguments: `int end_node` Returns the cost of the Hamiltonian path from 0 to end_node. |\n| [`HamiltonianPath`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L490) | Return type: `std::vector\u003cint\u003e ` Arguments: `int end_node` Returns the shortest Hamiltonian path from 0 to end_node. |\n| [`HamiltonianPath`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L498) | Return type: `void ` Arguments: `std::vector\u003cPathNodeIndex\u003e* path` Deprecated API. Stores HamiltonianPath(BestHamiltonianPathEndNode()) into \\*path. |\n| [`HamiltonianPathSolver`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L479) | Return type: `explicit ` Arguments: `CostFunction cost` \u003cbr /\u003e |\n| [`HamiltonianPathSolver`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L480) | \u003cbr /\u003e Arguments: `int num_nodes, CostFunction cost` \u003cbr /\u003e |\n| [`IsRobust`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L511) | Return type: `bool ` Returns true if there won't be precision issues. This is always true for integers, but not for floating-point types. |\n| [`TravelingSalesmanCost`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L501) | Return type: `CostType ` Returns the cost of the TSP tour. |\n| [`TravelingSalesmanPath`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L504) | Return type: `std::vector\u003cint\u003e ` Returns the TSP tour in the vector pointed to by the argument. |\n| [`TravelingSalesmanPath`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L507) | Return type: `void ` Arguments: `std::vector\u003cPathNodeIndex\u003e* path` Deprecated API. |\n| [`VerifiesTriangleInequality`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/hamiltonian_path.h#L514) | Return type: `bool ` Returns true if the cost matrix verifies the triangle inequality. |"]]
