Class TravelingSalesman

java.lang.Object
topics.greedy.tsp.TravelingSalesman
public class TravelingSalesman extends Object

Traveling Salesman

Implements the "Nearest Neighbor" greedy strategy to approximate the shortest Hamiltonian cycle in a weighted graph.

The Greedy Trap

This algorithm is extremely fast O(N²), but it is sub-optimal. By picking the closest city at every step, the salesman often finds himself trapped at the end of the tour with no choice but to take an extremely expensive edge to return to the starting city.

Author:
vicegd

  • Constructor Details

    • TravelingSalesman

      public TravelingSalesman()

  • Method Details

    • solve

      public SalesmanSolution solve(int[][] weights, int startNode)
      Executes the Nearest Neighbor heuristic. * @param weights Adjacency matrix of the graph.
      Parameters:
      startNode - The starting city index.
      Returns:
      A solution object containing the path and the total cost.