Кратчайшие пути из одной вершины

Для решения будем использовать алгоритм Дейкстры (алгоритм поиска кратчайшего пути из одной вершины).

#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define word unsigned int
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
int min(int n)
{
	int i, result;
	for(i=0;i<n;i++)
		if(!(flag[i])) result=i;
	for(i=0;i<n;i++)
		if((l[result]>l[i])&&(!flag[i])) result=i;
	return result;
}
word minim(word x, word y)
{
	if(x<y) return x;
	return y;
}
void main()
{
cout<<"Avialiniya predostavlyaet poleti v Moskvi, Tokio, London, Paris, Pekin"<<endl;
cout<<"esli bilet=0, znachit Avialiniya ne predostavlyaet poleti v etot gorod"<<endl;
	n=5;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++) c[i][j]=0;
	c[0][1]=4; cout<<"Bilet ot  Moskvi do Tokio =    ";	cout<<c[0][1]<<endl;
	c[0][2]=8; cout<<"Bilet ot  Moskvi do Londona =  ";	cout<<c[0][2]<<endl;
	c[0][3]=2; cout<<"Bilet ot  Moskvi do Paris =    ";	cout<<c[0][3]<<endl;
	c[0][4]=1; cout<<"Bilet ot  Moskvi do Pekina =   ";	cout<<c[0][4]<<endl;
	c[1][2]=0; cout<<"Bilet ot  Tokio do Londona =   ";	cout<<c[1][2]<<endl;
	c[1][3]=1; cout<<"Bilet ot  Tokio do Paris =     ";	cout<<c[1][3]<<endl;
	c[1][4]=3; cout<<"Bilet ot  Tokio do Pekina =    ";	cout<<c[1][4]<<endl;
	c[2][3]=5; cout<<"Bilet ot  Londona do Paris =   ";	cout<<c[2][3]<<endl;
	c[2][4]=2; cout<<"Bilet ot  Londona do Pekina =  ";	cout<<c[2][4]<<endl;
	c[3][4]=1; cout<<"Bilet ot  Paris do Pekina =    ";	cout<<c[3][4]<<endl;
	cout<<"   ";
	for(i=0;i>xn;
	cout<<"Vvedite konechnuy gorod (Moskvi=1, Tokio=2, London=3, Paris=4, Pekin=5):"<<endl;
	cin>>xk;
	xk--;
	xn--;
	if(xn==xk)
	{
		cout<<"Nachalnaya I konechnaya goroda sovpadayt."<<endl;
		getch();
		return;
	}

	for(i=0;i<n;i++)
	{
		flag[i]=0;
		l[i]=65535;
	}
	l[xn]=0;
	flag[xn]=1;
	p=xn;
	itoa(xn+1,s,10);
		for(i=1;i<=n;i++)
		{
			strcpy(path[i],"X");
			strcat(path[i],s);
		}
		do
		{
			for(i=0;i<n;i++)
				if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
				{
					if(l[i]>l[p]+c[p][i])
					{
						itoa(i+1,s,10);
						strcpy(path[i+1],path[p+1]);
						strcat(path[i+1],"-X");
						strcat(path[i+1],s);
					}
					l[i]=minim(l[i],l[p]+c[p][i]);
				}
			p=min(n);
			flag[p]=1;
		}
		while(p!=xk);
	if(l[p]!=65535)
	{
		cout<<"Put: "<<path[p+1]<<endl;
		cout<<"Stoimost puti: "<<l[p]<<endl;
	}
	else
		cout<<"takogo puti ne syshestvuet!"<<endl;
	getch();
}
Задачи
