TspMetricMstAppx (JGAlgo - Parent 0.5.1-SNAPSHOT API)

java.lang.Object
- com.jgalgo.alg.shortestpath.TspAbstract
- - com.jgalgo.alg.shortestpath.TspMetricMstAppx

All Implemented Interfaces:

Tsp
```
public class TspMetricMstAppx
extends TspAbstract
```
Metric TSP \(2\)-approximation using minimum spanning trees.
An MST weight of a graph is less or equal to the optimal TSP tour weight. By doubling each edge in such an MST and finding an Eulerian tour on these edges a tour can be found with weight at most \(2\) times the optimal TSP tour weight. In addition, shortcuts are used if vertices are repeated in the initial Eulerian tour - this is possible only in the metric special case.
This algorithm can only accept graphs and weight functions that satisfy the metric condition: every three vertices \(u,v,w\) should satisfy \(d((u,v)) + d((v,w)) \leq d((u,w))$ where \(d(\cdot)\) is the distance of the shortest path between two vertices. This condition is not validated for performance reason, but graphs that do not satisfy this condition will result in an undefined behaviour.
The running of this algorithm is \(O(n^2)\) and it achieve \(2\)-approximation to the optimal TSP solution.

Author:

Barak Ugav

- Constructor Summary
  
  Constructors
  Constructor Description
  
  TspMetricMstAppx()
  Create a new TSP \(2\)-approximation algorithm.
- Method Summary
  - Methods inherited from class com.jgalgo.alg.shortestpath.TspAbstract
    computeShortestTour
  - Methods inherited from class java.lang.Object
    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - TspMetricMstAppx
```
public TspMetricMstAppx()
```
    Create a new TSP \(2\)-approximation algorithm.