cheap.cpp

图论经典问题——哈密尔顿回路的便宜算法的实现

#include"iostream.h"
#include"stdio.h"
int ifover(int *p)
{
	int i=1;
	while(p[i-1])
		i++;
	if(i>=6)
		return 1;
	else
		return 0;
}
void main()
{
//	int a[5][5]={0,42,33,52,29,42,0,26,38,49,33,26,0,34,27,52,38,34,0,35,29,49,27,35,0};
	int a[5][5]={0,18,35,25,27,18,0,23,21,19,35,23,0,17,28,25,21,17,0,24,27,19,28,24,0};
	int i,j,cheapest[5][5]={0},mini,minj;
	int cheap[5]={0},l[2]={0},key;
	int city;
	char CITY;
	while(1)
	{
	cout<<"请输入旅行路线的起始城市："<<endl;
	cout<<"1,A城市"<<endl;
	cout<<"2,B城市"<<endl;
	cout<<"3,C城市"<<endl;
	cout<<"4,D城市"<<endl;
	cout<<"5,E城市"<<endl;
	cin>>city;
	if(city>0&&city<6)
		break;
	else
		cout<<"输入错误,请重新输入:"<<endl;
	}
	cheap[0]=city;
	while(!ifover(cheap))
	{
		i=0;
		mini=cheap[0];
		minj=cheap[0]+1;

	while(cheap[i])
	{
		for(j=0;j<5;j++)
			if(cheap[i]!=j+1&&a[cheap[i]-1][j]<a[mini-1][minj-1]&&mini!=minj)
			{
				mini=cheap[i];
				minj=j+1;
			}
		
			i++;
	}
	cheapest[mini-1][minj-1]=a[mini-1][minj-1];
	cheapest[minj-1][mini-1]=a[mini-1][minj-1];
	a[mini-1][minj-1]=9999;
	a[minj-1][mini-1]=9999;	
	cheap[i]=minj;

	for(i=0,j=0;cheap[i];i++)
		if(cheapest[cheap[i]-1][mini-1]&&cheap[i]!=minj)
		{
			l[j]=cheap[i];
			j++;
		}
	 if(l[0]&&!l[1])
	{
		cheapest[l[0]-1][minj-1]=a[minj-1][l[0]-1];
		cheapest[minj-1][l[0]-1]=a[l[0]-1][minj-1];
		a[l[0]-1][minj-1]=9999;
		a[minj-1][l[0]-1]=9999;
	}

	 if(l[1])
		if(a[l[1]-1][minj-1]-cheapest[l[1]-1][mini-1]>a[l[0]-1][minj-1]-cheapest[l[0]-1][mini-1])
		{
			cheapest[l[0]-1][mini-1]=0;
			cheapest[mini-1][l[0]-1]=0;
			cheapest[l[0]-1][minj-1]=a[l[0]-1][minj-1];
			cheapest[minj-1][l[0]-1]=a[l[0]-1][minj-1];

		}
		else
		{
			cheapest[l[1]-1][mini-1]=0;
			cheapest[mini-1][l[1]-1]=0;
			cheapest[l[1]-1][minj-1]=a[l[1]-1][minj-1];
			cheapest[minj-1][l[1]-1]=a[l[1]-1][minj-1];

		}

	}
	cout<<"旅行商的最佳路径为："<<endl;
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
			cout<<cheapest[i][j]<<"   ";
		cout<<endl;
	}
	for(i=0;i<4;i++)
		for(j=i+1;j<5;j++)
		{
			if(cheapest[cheap[i]-1][cheap[j]-1]&&j>i+1)
			{
			key=cheap[j];
			cheap[j]=cheap[i+1];
			cheap[i+1]=key;
			break;
			}
			if(cheapest[cheap[i]-1][cheap[j]-1])
				break;
				
		}
		for(i=0;i<5;i++)
		{
			switch(cheap[i])
			{
			case 1:
				{
					cout<<"A-->";
					if(i==0)
						CITY='A';
					break;
				}	
			case 2:
				{
					cout<<"B-->";
					if(i==0)
						CITY='B';
					break;
				}
			case 3:
				{
					cout<<"C-->";
					if(i==0)
						CITY='C';
					break;
				}
			case 4:
				{
					cout<<"D-->";
					if(i==0)
						CITY='D';
					break;
				}
			case 5:
				{
					cout<<"E-->";
					if(i==0)
						CITY='E';
					break;
				}
			default:
				break;
			}
			if(i==4)
				cout<<CITY<<endl;
		}
		



	
}