travel.c

算法小作业

#include <stdio.h>
#include <stdlib.h>

int dis[][6] = {
	0,10,20,30,40,50,
	12,0,18,30,25,21,
	23,19,0,5,10,15,
	34,32,4,0,8,16,
	45,27,11,10,0,18,
	56,22,16,20,12,0
};

//动态规划，计算从current城市，到终点的最短路径
//city是当前的决策变量集合，city[0]代表可选城市数，1、2、3.。。代表可选城市
//返回数组min_Path，min_Path[0]代表最短路径长度，1、2、3、4、5记录最短路径
int *travel(int current,int * city)
{
	int i,j,k;
	int *temp;
	int min_Path[6]={9999,0,0,0,0,0};

	int newCitises[6];

	newCitises[0] = city[0]-1;

	if (city[0] == 0)       //到达最后一个节点，返回从该节点回到起点0的距离
	{
		min_Path[0] = dis[current][0];
		return min_Path;
	}

	for (i= 1;i<=city[0];i++)       //遍历决策变量集合
	{
		for (j=1;j<i;j++)             //计算下一个决策变量集合，即减去当前节点
		{
			newCitises[j]=city[j];
		}
		for(k=i+1;k<=city[0];k++)
		{
			newCitises[k-1] =city[k];
		}


		temp = travel(city[i],newCitises);		//递归，计算从current城市，若经过city[i],到终点的最短路径
		temp[0] +=dis[current][city[i]];       //递推式： travel(current,City)= min{dis[current][city[i]]+travel(city[i],newCitises)}
		temp[6-city[0]] = city[i];				//记录路径

		if (min_Path[0]>temp[0])
		{	
			memcpy(min_Path,temp,6*sizeof(int));   //记录下最短的
		}
		
	}


	return min_Path;   //返回
}

void main(void)
{
	int city[6] = {5,1,2,3,4,5};
	int i;
	int *shortest_Path;
	int min[6];

	shortest_Path = travel(0,city); //1.注意一下函数返回值是指针的用法；
									//2、下面打印时不能直接答应shortest_Path[i],  要暂存在min中，否则值会被修改，亦是指针问题

	memcpy(min, shortest_Path,6*sizeof(int));      

	printf("%d\n1-->",min[0]);
	for( i = 1;i< 6;i++)
	{
		printf("%d-->",min[i]+1);
	}
	printf("1\n");

}