V - the graph vertex typeE - the graph edge typepublic class TwoApproxMetricTSP<V,E> extends Object implements TSPAlgorithm<V,E>
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?". In the metric TSP, the intercity distances satisfy the triangle inequality.
This is an implementation of the folklore algorithm which returns a depth-first ordering of the minimum spanning tree. The algorithm is a 2-approximation assuming that the instance satisfies the triangle inequality. The implementation requires the input graph to be undirected and complete. The running time is $O(|V|^2 \log |V|)$.
See wikipedia for more details.
| Constructor and Description |
|---|
TwoApproxMetricTSP()
Construct a new instance
|
| Modifier and Type | Method and Description |
|---|---|
GraphPath<V,E> |
getTour(Graph<V,E> graph)
Computes a 2-approximate tour.
|
public GraphPath<V,E> getTour(Graph<V,E> graph)
getTour in interface HamiltonianCycleAlgorithm<V,E>getTour in interface TSPAlgorithm<V,E>graph - the input graphIllegalArgumentException - if the graph is not undirectedIllegalArgumentException - if the graph is not completeIllegalArgumentException - if the graph contains no verticesCopyright © 2018. All rights reserved.