Traveling Salesman Problem - Algorithm

Input : Number of cities n and array of costs c(i,j) i,j=1,..n (We begin from city number 1)
Output:Vector of cities and total cost.

• (* starting values *)
• C=0
• cost=0
• visits=0
• e=1 (*e=pointer of the visited city)
• (* determination of round and cost)
• for r=1 to n-1 do
  • choose of pointer j with
  • minimum=c(e,j)=min{c(e,k);visits(k)=0 and k=1,..,n}
  • cost=cost+minimum
  • e=j
  • C(r)=j
• end r-loop
• C(n)=1
• cost=cost+c(e,1)

We can find situations in which the TSP algorithm don't give the best solution.We can also succeed on improving the algorithm.For example we can apply the algorithm t times for t different cities and keep the best round every time.We can also unbend the greeding in such a way to reduce the algorithm problem ,that is there is no room for choosing cheep sides at the end of algorithm because the cheapest sides have been exhausted.

HTML PAGE DIRECTOR :Papaioannou Panagiotis