最后加入路径的代码.c

旅行商问题 某售货员要到若干城市去推销商品

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAX 1000000
#define INFINITY 100000

int d[21][MAX]={INFINITY};
int pos[21][MAX];
int main(){
	int i,j,k,t,n,tempk,tmppos;//tmpk用于记忆最小值时的点
	long min;
	int c[21][21]={0};
	char str[100];
	
	printf("Input the filename:\n");
	scanf("%s",str);
	if(freopen(str,"r",stdin)==NULL){
		printf("open file error\n");
		printf("文件名错误的一般原因是:1.请输入双杠号	如:c:\\TSP4.txt\n");
		exit(1);
	};
 	scanf("%d",&n);

	for(i=0;i<n;i++)
		for(j=0;j<n;j++){
			scanf("%d",&c[i][j]);
			if(c[i][j]==0) c[i][j]=INFINITY;
		}
	
	for(i=1;i<n;i++){
		d[i][0]=c[i][0];

//		printf("%d ",d[i][0]);
		}
//	printf("\n");
	t=1;
	for(i=1;i<n;i++)
		t=t*2;					//用二进制来表示有还是没有
	t=t-1;
	
	for(i=1;i<=t;i++){

		for(j=1;j<=n-1;j++){
			min=INFINITY;
			if(((i>>(j-1))&1)==0){		//j不在集合[I]中
				tempk=-1;				
				for(k=1;k<=n;k++)	{
				if(((i>>(k-1))&1)!=0)	// 对集合[i]中的每个元素
					if(c[j][k]+d[k][i-(1<<(k-1))]<min){
						min=d[k][i-(1<<(k-1))]+c[j][k];
						tempk=k;	//tempk记住了D[J][I]中的最小值
					}
				}
				d[j][i]=min;
				pos[j][i]=tempk;
				
			}//if((i&(1<<j)
//			printf("%d ",min);
			}//for j

//		printf("\n");
	}//for i
//	printf("t is %d\n",t);
	
	min=INFINITY;
	for(i=1;i<=n-1;i++)		//计算起始结点,即第一个点
		if(min>c[i][0]+d[i][t-(1<<(i-1))]){
			min=c[i][0]+d[i][t-(1<<(i-1))];
			tmppos=i;
		}
	printf("最短路径长度 %d\n",min);
	
	printf("路径是: ");
	printf("1,");
	printf("%d,",tmppos+1);
	i=t;


	for(j=n-1;j>1;j--){
		i=i-(1<<(tmppos-1));
		printf("%d,",pos[tmppos][i]+1);	//加1是因为我的数组是从0开始的,而结点号
		tmppos=pos[tmppos][i];
	}


	//test pos[j][i]		这段代码是用来做DEBUG的.现在把它注释掉
/*	freopen("e:\\1.txt","w",stdout);
	for(i=1;i<=n;i++){
		for(j=1;j<=t;j++)
			printf("%d ",pos[i][j]);
		printf("\n");
	}
*/
	return 1;
}