HeldKarpTSP (JGraphT : a free Java graph library)

java.lang.Object
- org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
- - org.jgrapht.alg.tour.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 HamiltonianCycleAlgorithmBase<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()
- 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 org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
    checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
  - Methods inherited from class java.lang.Object
    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - HeldKarpTSP
```
public HeldKarpTSP()
```
- Method Detail
  - getTour
```
public GraphPath<V,E> getTour(Graph<V,E> graph)
```
    Computes a minimum-cost Hamiltonian tour.
    
    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