1.5.4 Traveling Salesman Problem

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A weighted graph G .

Problem: Find the cycle of minimum cost visiting all of the vertices of G exactly once.

Implementations

  • TSP solvers (C) (rating 8)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 6)
  • Discrete Optimization Methods (Pascal) (rating 5)
  • Combinatorica (Mathematica) (rating 3)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 3)

    Related Problems

  • Convex Hull
  • Hamiltonian Cycle
  • Minimum Spanning Tree
  • Satisfiability

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .