Package org.jgrapht.alg.tour

Class HeldKarpTSP<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    HamiltonianCycleAlgorithm<V,​E>
    public class HeldKarpTSP<V,​E>
extends java.lang.Object
implements HamiltonianCycleAlgorithm<V,​E>
    A dynamic programming algorithm for the 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?".

    This is an implementation of the Held-Karp algorithm which returns a optimal, minimum-cost Hamiltonian tour. The implementation requires the input graph to contain at least one vertex. The running time is $O(2^{|V|} \times |V|^2)$ and it takes $O(2^{|V|} \times |V|)$ extra memory.

    See wikipedia for more details about TSP.

    See wikipedia for more details about the dynamic programming algorithm.

    Author:
    Alexandru Valeanu

    • Constructor Summary

      Constructors 
      Constructor Description
      HeldKarpTSP()
      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 minimum-cost Hamiltonian tour.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • HeldKarpTSP

        public HeldKarpTSP()
        Construct a new instance

    • Method Detail

      • getTour

        public GraphPath<V,​E> getTour​(Graph<V,​E> graph)
        Computes a minimum-cost Hamiltonian tour.
        Specified by:
        getTour in interface HamiltonianCycleAlgorithm<V,​E>
        Parameters:
        graph - the input graph
        Returns:
        a minimum-cost tour if one exists, null otherwise
        Throws:
        java.lang.IllegalArgumentException - if the graph contains no vertices
        java.lang.IllegalArgumentException - if the graph contains more than 31 vertices