Package com.jgalgo.alg.shortestpath

Interface Tsp

All Known Implementing Classes:
TspAbstract, TspMetricMatchingAppx, TspMetricMstAppx
public interface Tsp
Traveling Salesman Problem (TSP) algorithm.

Given a graph, the traveling salesman problem asks what is the shortest tour that visit all the vertices and returns to the starting vertex. The problem itself is NP-hard, but various approximation algorithms exists.

The metric version of TSP is a special case in which the distances satisfy the triangle inequality and the distances are symmetric.

Author:
Barak Ugav
See Also:

  • Method Details

    • computeShortestTour

      <V, E> Optional<Path<V,E>> computeShortestTour(Graph<V,E> g, WeightFunction<E> w)
      Compute the shortest tour that visit all vertices.

      Note that this problem is NP-hard and therefore the result is only the best approximation the implementation could find.

      If g is an IntGraph, an optional of IPath is returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph containing all the vertices the tour must visit, using its edges
      w - an edge weight function
      Returns:
      an optional of the tour calculated, or an empty optional if no such path was found