Class HamiltonianCycle


  • public class HamiltonianCycle
    extends java.lang.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
    • Constructor Detail

      • HamiltonianCycle

        public HamiltonianCycle()
    • Method Detail

      • getApproximateOptimalForCompleteGraph

        public static <V,​E> java.util.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.