V
 the graph vertex typeE
 the graph edge typepublic class ChristofidesThreeHalvesApproxMetricTSP<V,E> extends Object implements HamiltonianCycleAlgorithm<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 Christofides algorithm. The algorithms is a $3/2$approximation assuming that the input graph satisfies triangle inequality and all edge weights are nonnegative. The implementation requires the input graph to be undirected and complete. The worst case running time complexity is $\mathcal{O}(V^3E)$.
The algorithm performs following steps to compute the resulting tour:
The following two observations yield the $3/2$ approximation bound:
For more details, see Christofides, N.: Worstcase analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Administration, Carnegie Mellon University (1976).
Constructor and Description 

ChristofidesThreeHalvesApproxMetricTSP()
Empty constructor

Modifier and Type  Method and Description 

GraphPath<V,E> 
getTour(Graph<V,E> graph)
Computes a $3/2$approximate tour.

public ChristofidesThreeHalvesApproxMetricTSP()
public GraphPath<V,E> getTour(Graph<V,E> graph)
getTour
in interface HamiltonianCycleAlgorithm<V,E>
graph
 the input graphIllegalArgumentException
 if the graph is not undirectedIllegalArgumentException
 if the graph is not completeIllegalArgumentException
 if the graph contains no verticesCopyright © 2019. All rights reserved.