Package com.jgalgo.alg.shortestpath

Class TspMetricMstAppx

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 Details

    • TspMetricMstAppx

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