ALGORITHME DU VOYAGEUR ( NON OPTIMISÉ )

#include<iostream.h>
#include<string.h>
#include<math.h>

const int nbmaxville=100;


struct ville
{
	char nom[16];
	double x,y;
};


struct liste
{
	int nbville;
	ville town[nbmaxville];
};


double distance(ville v1,ville v2)
{
	double x1,y1;
	x1=v1.x-v2.x;
	y1=v1.y-v2.y;
	return (sqrt(x1*x1+y1*y1));
}


void saisirville(ville &city)
{
	cout<<"Entrez le nom de la fille : ";cin>>city.nom;
	cout<<"Entrez l'abscisse de la fille : ";cin>>city.x;
	cout<<"Entrez l'ordonnee de la fille : ";cin>>city.y;
}


void saisirliste(liste &listeville)
{
	int i,j;
	ville city;
	bool cestbon;
	do
	{cout<<"combien de fille foulez fous entrer?";cin>>listeville.nbville;}
	while ((listeville.nbville<0)||(listeville.nbville>100));
	for (i=0;i<listeville.nbville;i++)
	{
		do
		{
			saisirville(city);
			for (j=0;j<i;j++)
			{
				if ((strcmp(listeville.town[j].nom,city.nom)==0)||((listeville.town[j].x==city.x)&&(listeville.town[j].y==city.y)))
				{
					cout<<"Nom ou emplacement deja vendu."<<endl;
					cestbon=false;
				}
				else cestbon=true;
			}
		}while (cestbon==false);
		listeville.town[i]=city;
	}
}


void supprimeville(liste &listeville,ville &city)
{
	int i,j;
	for (i=0;i<listeville.nbville;i++)
	{
		if ((strcmp(listeville.town[i].nom,city.nom))==0)
		{
			listeville.nbville--;
			for (j=i;j<listeville.nbville;j++)
			{
				listeville.town[j]=listeville.town[j+1];
			}
		}
	}
}

void stadtplusproche(liste &listeciudad,int &pproche,double &dist)
{
	int i;
	pproche=0;
	dist=distance(listeciudad.town[0],listeciudad.town[listeciudad.nbville-1]);
	for (i=1;i<listeciudad.nbville-1;i++)
	{
		if (distance(listeciudad.town[i],listeciudad.town[listeciudad.nbville-1])<dist)
		{
			dist=distance(listeciudad.town[i],listeciudad.town[listeciudad.nbville-1]);
			pproche=i;
		}
	}
}


void main()
{
	int i,placeville;
	bool existe;
	double disttot=0,dist;
	ville stadt;
	liste listestadt;
	existe=false;
	cout<<"Bonjour, fous allez bien?"<<endl;
	saisirliste(listestadt);
	do
	{
		cout<<"Feuillez saisir fotre fille de depart? ";cin>>stadt.nom;
		for (i=0;i<listestadt.nbville;i++)
		{
			if ((strcmp(stadt.nom,listestadt.town[i].nom))==0) 
			{
				stadt=listestadt.town[i];
				placeville=i;
				existe=true;
			}
		}
	if (existe==false) cout<<"Fous nous mentez! Cette Stadt n'existe pas! Donnez nous une fille qui existe! Nous afons les moyens de fous faire barler!"<<endl;
	} while (existe==false);
	cout<<"Premiere stadt : "<<stadt.nom<<endl;
	while (listestadt.nbville>1)
	{
		listestadt.town[placeville]=listestadt.town[listestadt.nbville-1];
		listestadt.town[listestadt.nbville-1]=stadt;
		stadtplusproche(listestadt,placeville,dist);
		disttot+=dist;
		supprimeville(listestadt,stadt);
		stadt=listestadt.town[placeville];
		cout<<"Stadt suivante : "<<stadt.nom<<endl;
		cout<<"Distance entre les deux derniere ville : "<<dist<<endl;
	}
	cout<<endl;
	cout<<"Distance totale : "<<disttot<<endl<<endl;
}