Necessary condition for shortest path of TSP
Hong Yu-zhen · Journal of Hohai University · 2006
For the asymmetrical traveling salesman problem(TSP) with n cities to be visited,a square matrix with n rows and n columns was constructed.Different vertex in each row represented the same city,and n vertex in each column represented n different cities.Taking one city from each column of the 1~(st) colunm to the k~(th) column in this matrix with only one city at most taken from a row,the k cities formed a traveling salesman's path with length k.It is deduced that,if the shortest path with length n-1 was found,any path of length k(k=1,2,…,n-2) on this path was definitely the shortest path.The result provides a basis for further study of the algorithm for the traveling salesman problem.