최소 순회 경로가 있다면 어디서 출발하든간에 원래 위치로 돌아오기만 하면 이동한 거리는 같겠죠?

만일 다른 노드에서 시작해서 만들 수 있는 더 짧은 경로가 있다고 가정해봅시다.

그러면 그 경로는 그대로 두고 시작점만 달리해도, 즉 처음에 시작한 노드에서 그 경로를 따라가도 똑같은 길이가 나옵니다.

그래서 처음에 시작한 노드에서 찾은 경로가 해당 노드에서 시작했을 때의 최단 경로였다는 가정에 모순이므로, 그 경로는 전체 시작점에 대해 최단일 수밖에 없습니다.

다들 감사합니다! 그림과 설명이 둘다 있으니 이해가 되네요!

글쎄요.. 약간 의아한데요. 이 TSP 문제의 경우 양방향 그래프가 아니며 문제의 조건에서 도시 간의 왕복이 항상 가능하지 않다고 명시하고 있습니다.  

만약 1에서 출발한다고 했을 때 어떤 임의의 노드에서 1로 오는 길이 없을 경우(가중치가 0일 경우) 다른 노드에서 출발한 경우의 답과 달라질 수 있는거 아닌가요?

제가 위에 만들어 놓은 그림의 왼쪽과 같은 답이 존재한다면, 1->2, 2->3, ..., 6->1로 가는 길이 있다는 뜻입니다. 따라서 2->3, 3->4, ..., 1->2로 가는 길이 있습니다.

아 그렇군요. 댓글 감사합니다