org.jgrapht.alg
Class HamiltonianCycle
java.lang.Object
org.jgrapht.alg.HamiltonianCycle
public class HamiltonianCycle
- extends Object
This class will deal with finding the optimal or approximately optimal
minimum tour (hamiltonian cycle) or commonly known as the Traveling
Salesman Problem.
- Author:
- Andrew Newell
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
HamiltonianCycle
public HamiltonianCycle()
getApproximateOptimalForCompleteGraph
public static <V,E> List<V> getApproximateOptimalForCompleteGraph(SimpleWeightedGraph<V,E> g)
- This method will return an approximate minimal traveling salesman tour
(hamiltonian cycle). This algorithm requires that the graph be complete
and the triangle inequality exists (if x,y,z are vertices then
d(x,y)+d(y,z)
- Type Parameters:
V
- E
- - Parameters:
g
- is the graph to find the optimal tour for.
- Returns:
- The optimal tour as a list of vertices.
Copyright © 2013. All rights reserved.