p4.0419086

以最近通路法,及逐步修正法搜索通路,求出最小权的哈密顿通路或者哈密顿回路,既货廊问题 请将数字改为txt后缀

/*====================program description=================*/
/*name:p4.c */
/*goal:用最临近法求最佳回路 */
/*========================================================*/

//==========================================================
//头文件
//==========================================================
#include <conio.h>        /* 此头函数请不要删除 */
#include <stdio.h>


//==========================================================
//全局变量
//==========================================================
int a[400][400];
int flo[40][40];
int h[40];//纪录各点的点号
int a_h[40];
int min_length=3000000;
int a_length;
int num;
int sign[40];
int k;
int path[40][40];

//==========================================================
//读入矩阵
//==========================================================
int loadin(int (*p)[400])//读入矩阵函数
{
   int i,j;
   FILE *fp;
   int n;
   char path[40];
   
   //读入路径，打开文件
   printf("input the path of the file\n");
   scanf("%s%*c",path);
   fp=fopen(path,"r");
   
   while(fp==NULL)
   {
        printf("cannot open the file,input again\n");
        scanf("%s%*c",path);
        fp=fopen(path,"r");
   }

   fscanf(fp,"%d",&n);
   
   //输入矩阵
   for (i=0;i<n;i++)	   
   {
	   p[i][i]=0;
	   for(j=i+1;j<n;j++)
	   {
	       fscanf(fp,"%d",&p[i][j]);
	       p[j][i]=p[i][j];
	   }
   }
   printf("\n");
   return n;
}

//=======================================================
//floyd函数
//=======================================================
void floyd(int (*p)[400],int m)//生成最短路径矩阵
{
	int i,j,k;

	//对最短路径矩阵赋初值(k=-1)
	for(i=0;i<m;i++)
	{
		for(j=0;j<m;j++)
		{
			flo[i][j]=p[i][j];
			path[i][j]=0;
		}
	}
	
	//生成最短路径矩阵
	for(k=0;k<m;k++)
	{
		for(i=0;i<m;i++)
			
		{
			for(j=0;j<m;j++)
			{
				if(flo[i][k]+flo[k][j]<flo[i][j])
				{
					flo[i][j]=flo[i][k]+flo[k][j];
					path[i][j]=k;
				}
			}
		}
	}
	/*for(i=0;i<num;i++)
	{
		for(j=0;j<num;j++)
		{
			printf("%d  ",flo[i][j]);
		}
		printf("\n");
	}*/
	printf("the mission(floyd) has been completed\n");
}
//=======================================================
//寻找最佳路径函数
//=======================================================
void search(int x)
{
	int i=0;
	int j;
	int min,node;
	//初始化
	for(j=0;j<40;j++)
	{
		a_h[j]=-1;
		sign[j]=0;
	}
	a_h[0]=x;
	sign[x]=1;
	min=30000;
	node=-1;
	a_length=0;
	
	i=0;
	while(i<num)
	{
		for(j=0;j<num;j++)
		{
			if(min>flo[a_h[i]][j] && sign[j]!=1 && flo[a_h[i]][j]!=0)
			{
				min=flo[a_h[i]][j];
				node=j;
			}
		}
		
		i++;
		a_h[i]=node;
		sign[node]=1;
		if(min<30000)
		{
			a_length=a_length+min;
		}
		min=30000;
	}

}

//=======================================================
//output function(已废除）)
//=======================================================
/*void output(int m)
{
	if(m=k)
	{
		printf("--->%d",m+1);
		output(next[m]);
	}
	else
	{
		printf("--->%d",m+1);
		return;
	}
}*/

//=======================================================
//主函数
//=======================================================
void main()
{
	int i,j;
	
	num=loadin(a);//读入矩阵
	floyd(a,num);//转换为最短路径矩阵
	for(i=0;i<num;i++)//在各起点最短中选择最短
	{
		search(i);
		if(min_length>a_length)
		{
			k=i;
			min_length=a_length;
			for(j=0;j<num;j++)
			{
				h[j]=a_h[j];
			}
		}
	}
	//输出
	for(i=0;i<num;i++)
	{
		printf("%d	",h[i]+1);
	}
	printf("the length is %d\n",min_length);

}