Click here to Skip to main content
14,303,648 members

Solution to Travelling Salesman Problem

Rate this:
1.54 (18 votes)
Please Sign up or sign in to vote.
1.54 (18 votes)
21 Jan 2005
Solution to a Travelling Salesman problem using Hamiltonian circuit, the efficieny is O(n^4) and I think it gives the optimal solution.


Hereby, I am giving a program to find a solution to a Traveling Salesman Problem using Hamiltonian circuit, the efficiency is O (n^4) and I think it gives the optimal solution. Though I have provided enough comments in the code itself so that one can understand the algorithm that I m following, here I give the pseudocode.

Problem Statement

Find the order of cities in which a salesman should travel in order to start from a city, reaching back the same city by visiting all rest of the cities each only once and traveling minimum distance for the same.

ALT statement: Find a Hamiltonian circuit with minimum circuit length for the given graph.


G: Symmetric weighted undirectional graph with,

  • Number of vertices = No. of cities
  • Number of links = Number of paths
  • Weight of the link = Distance of the path.


for each vertex V in the graph G
  for each vertex V_N in the graph G such that V and V_N are different
   mark all vertices unvisited
   mark V as visited 
     for staring vertex as V and succeeding vertex as V_N, find circuit 
          such that path staring from V_N in that circut yeilds minimum 
          pathlength from V_N for all unvisited vertices by 
          visiting each vertex.( this path is obtained by greedy method).
       if currently obtained circuit length <= MIN_CKT_LENGTH then
         set MIN_CKT_LENGTH=newly obtained value
         copy the new circuit as hamiltonion circuit
       end if
     end for V_N
   end for V

code segment:

//for each vertex, S_V as a staring node

for(int S_V_id=0;S_V_id<n;S_V_id++)

      //for each and non start vertex as i
          //set all to unvisited
          // set staring vertex as visited
          //reset/init minimum circuit
          // obtain circuit for combination of S_V and i
          // if newer length is less than the previously
          //calculated min then set it as min and set the
          //current circuit in hamiltonion circuit



Image 1


infinity: 999
no. of cities: 4
no. of paths: 6

 S D Dist
path0: 0 1 2
path1: 0 2 4
path2: 0 3 3
path3: 1 2 3
path4: 1 3 6
path5: 2 3 1

Algorithm proceeds as follows:

VV_NV_N-pathckt_length, ckt
(started with INFI,-)
(started with INFI,-)


This might be the overrun for lower values of vertex count but for large values of n, it's surely less than the exhaustive search as n increases n^4 < n! for n>6.

The optimality is the issue with this problem and as far as I am concerned, I think this algorithm yields the optimal Hamiltonian circuit if it exists at all.

Hereby I ask you people to evaluate my algorithm for different sets of test cases. In case of failure, please inform me with the set of input values, answer found by my code and the actual optimal answer.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

omkar joshi
India India
Engg Student

Comments and Discussions

Questionthanks Pin
saeedmag4-Jul-12 6:47
membersaeedmag4-Jul-12 6:47 
QuestionSome question. Pin
Spas22110-Jan-12 2:29
memberSpas22110-Jan-12 2:29 
QuestionDocumentation Pin
garzon326-Jun-11 10:00
membergarzon326-Jun-11 10:00 
Questionheuristic Pin
Tamas Bege15-Dec-10 3:07
memberTamas Bege15-Dec-10 3:07 
hamid_ss28-May-10 11:53
memberhamid_ss28-May-10 11:53 
GeneralMinor change !! Pin
patson3318-Mar-10 14:01
memberpatson3318-Mar-10 14:01 
GeneralAlgorithm is not optimal Pin
KHDev4u10-Mar-06 12:20
memberKHDev4u10-Mar-06 12:20 
GeneralRe: Algorithm is not optimal Pin
omkar joshi11-Mar-06 0:00
memberomkar joshi11-Mar-06 0:00 
GeneralRe: Algorithm is not optimal Pin
sirb27-Nov-11 0:28
membersirb27-Nov-11 0:28 
QuestionP = NP? Pin
Cap'n Code22-Jan-05 6:21
memberCap'n Code22-Jan-05 6:21 
AnswerRe: P = NP? Pin
Rui A. Rebelo22-Jan-05 7:39
memberRui A. Rebelo22-Jan-05 7:39 
GeneralRe: P = NP? Pin
omkar joshi22-Jan-05 21:03
memberomkar joshi22-Jan-05 21:03 
AnswerRe: P = NP? Pin
omkar joshi22-Jan-05 21:03
memberomkar joshi22-Jan-05 21:03 
AnswerRe: P = NP? Pin
jbstjohn24-Jun-05 5:43
memberjbstjohn24-Jun-05 5:43 
GeneralRe: P = NP? Pin
Paul Conrad1-Jul-05 7:23
professionalPaul Conrad1-Jul-05 7:23 
GeneralRe: P = NP? Pin
Anonymous29-Aug-05 10:21
memberAnonymous29-Aug-05 10:21 
GeneralRe: P = NP? Pin
omkar joshi24-Jan-06 1:54
memberomkar joshi24-Jan-06 1:54 
GeneralRe: P = NP? Pin
omkar joshi24-Jan-06 1:27
memberomkar joshi24-Jan-06 1:27 
GeneralRe: P = NP? Pin
omkar joshi24-Jan-06 1:43
memberomkar joshi24-Jan-06 1:43 
GeneralRe: P = NP? Pin
jbstjohn9-Feb-06 4:16
memberjbstjohn9-Feb-06 4:16 
GeneralRe: P = NP? Pin
vishal_chauhan8-May-07 3:26
membervishal_chauhan8-May-07 3:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Posted 21 Jan 2005


31 bookmarked