org.jgrapht.alg.tour

Class HeldKarpTSP<V,E>

java.lang.Object

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>, TSPAlgorithm<V,E>

public class HeldKarpTSP<V,E>
extends Object
implements TSPAlgorithm<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 and Description
HeldKarpTSP() Construct a new instance

Method Summary

Modifier and Type	Method and 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>

Specified by:

getTour in interface TSPAlgorithm<V,E>

Parameters:

graph - the input graph

Returns:

a minimum-cost tour if one exists, null otherwise

Throws:

IllegalArgumentException - if the graph contains no vertices

IllegalArgumentException - if the graph contains more than 31 vertices