Package org.jgrapht.alg.tour

Class TwoApproxMetricTSP<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    HamiltonianCycleAlgorithm<V,​E>
    public class TwoApproxMetricTSP<V,​E>
extends java.lang.Object
implements HamiltonianCycleAlgorithm<V,​E>
    A 2-approximation algorithm for the metric TSP problem.

    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.

    Author:
    Dimitrios Michail

    • Constructor Summary

      Constructors 
      Constructor Description
      TwoApproxMetricTSP()
      Construct a new instance

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      GraphPath<V,​E> getTour​(Graph<V,​E> graph)
      Computes a 2-approximate tour.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • TwoApproxMetricTSP

        public TwoApproxMetricTSP()
        Construct a new instance

    • Method Detail

      • getTour

        public GraphPath<V,​E> getTour​(Graph<V,​E> graph)
        Computes a 2-approximate tour.
        Specified by:
        getTour in interface HamiltonianCycleAlgorithm<V,​E>
        Parameters:
        graph - the input graph
        Returns:
        a tour
        Throws:
        java.lang.IllegalArgumentException - if the graph is not undirected
        java.lang.IllegalArgumentException - if the graph is not complete
        java.lang.IllegalArgumentException - if the graph contains no vertices