Travelling Salesman Problem

Given a number of cities and the costs of traveling from any city to any other city, find the cheapest round-trip route that visits each city once and then returns to the starting city.

In other words, Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find the Hamiltonian cycle with the least weight.

Assumptions:

Cost is nonnegative

Triangle Inequality is satisfied

Implement an approximation algorithm

Input

No.of nodes

Weights/Costs between nodes

Starting node

Output:

The order of visit

Cost of the cycle

The testdata1 and testdata2 file contains the number of nodes and the edges < a b cost>.

For more details, mail to: dyana@cse.iitm.ernet.in