实验5_单源点最短路径问题.cpp

单源点最短路径

#include<iostream.h>


#define MAXVEX 25
#define $ 10000000


void out(int n)
{
	switch(n)	
	{	
	case 0: cout<<"乌鲁木齐";break;
	case 1: cout<<"西宁";break;		
	case 2: cout<<"兰州";break;		
	case 3: cout<<"呼和浩特";break;		
	case 4: cout<<"北京";break;				
	case 5: cout<<"天津";break;				
	case 6: cout<<"沈阳";break;
	case 7: cout<<"大连";break;
	case 8: cout<<"长春";break;
	case 9: cout<<"哈尔滨";break;
	case 10: cout<<"西安";break;
	case 11: cout<<"郑州";break;
	case 12: cout<<"徐州";break;
	case 13: cout<<"成都";break;
	case 14: cout<<"昆明";break;
	case 15: cout<<"贵阳";break;
	case 16: cout<<"南宁";break;
	case 17: cout<<"柳州";break;
	case 18: cout<<"株州";break;
	case 19: cout<<"广州";break;
	case 20: cout<<"深圳";break;
	case 21: cout<<"南昌";break;
	case 22: cout<<"福州";break;
	case 23: cout<<"上海";break;
	case 24: cout<<"武汉";break;
	}
}

void output(int dist[MAXVEX],int path[MAXVEX],int S[MAXVEX],int v0)//v0终点城市,一对多
{
	int i,k=0;
	for(i=0;i<MAXVEX;i++)
	{
		if(S[i]==1)
		{
			k=i;		
			while(k!=v0)
			{
				out(k);
				cout<<"<-";
				k=path[k];
			}
			out(k);
			cout<<'\t';			
			cout<<dist[i]<<endl;		
		}
		else
		{
			out(i);
			cout<<"<-";
			out(v0);
			cout<<'\t';	
			cout<<$<<endl;

		}
	}
}

void output(int dist[MAXVEX],int path[MAXVEX],int S[MAXVEX],int v0,int m)//v0起点城市，m终点城市
{
	int k=0;		
	if(S[m]==1)	
	{		
		k=m;		
		while(k!=v0)		
		{				
			out(k);				
			cout<<"<-";							
			k=path[k];			
		}			
		out(k);			
		cout<<'\t';		
		cout<<dist[m]<<endl;		
	}	
	else		
	{			
		out(m);			
		cout<<"<-";			
		out(v0);			
		cout<<'\t';
		//	cout<<i<<"<-"<<v0<<'\t';			
		cout<<$<<endl;	
	}
}
void ShortPath(int G[MAXVEX][MAXVEX],int dist[MAXVEX],int path[MAXVEX],int S[MAXVEX],int v0)  
{
	//dist[MAXVEX]={0};
	//path[MAXVEX]={0};
	//S[MAXVEX];//S[v]==0,点V不在S中，即已经求得了V0到V的最短路径
	int wmin,w,u,vnum;	
	for(w=0;w<MAXVEX;w++)
	{
		dist[w]=G[v0][w];//初始化 dist[]为v0到其余点的最短距离
		if(G[v0][w]<$)path[w]=v0;//初始化w的前驱结点为v0,if(G[v0][w]<$)则v0到w有直接路径		
	}
	for(w=0;w<MAXVEX;w++)S[w]=0;
	S[v0]=1;
	vnum=0;	//注意？？？？？？？？？？？？？？？
	while(vnum<MAXVEX-1)		
	{	
		wmin=$;//????????
		u=v0;	
		for(w=0;w<MAXVEX;w++)		
		{
			if(S[w]==0&&dist[w]<wmin)	//找到直接最短路径		
			{			
				u=w;
				wmin=dist[w];			
			}	
		}			
		S[u]=1;		//把点u加入S中,u为找到最短路径的终点		
		vnum++;	    //S中顶点个数加1
		for(w=0;w<MAXVEX;w++)		
		{
			if(S[w]==0&&dist[u]+G[u][w]<dist[w])			
			{//w不在S中且从v0经点u到w的距离小于v0直接到w的距离			
				dist[w]=dist[u]+G[u][w];//更新v0到w的距离			
				path[w]=u;	//w的前驱为u
			}
		}	
	}
} 

void main()
{
	int G[25][25]=
	{
		{0,$,1892,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//0 乌鲁木齐
		{$,0,216,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//1 西宁
		{1892,216,0,1145,$,$,$,$,$,$,676,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//2 兰州
		{$,$,1145,0,668,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//3 呼和浩特
		{$,$,$,668,0,137,$,$,$,$,$,695,$,$,$,$,$,$,$,$,$,$,$,$,$},//4 北京
		{$,$,$,$,137,0,704,$,$,$,$,$,674,$,$,$,$,$,$,$,$,$,$,$,$},//5 天津
		{$,$,$,$,$,704,0,397,305,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//6 沈阳
		{$,$,$,$,$,$,397,0,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//7 大连
		{$,$,$,$,$,$,305,$,0,242,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//8 长春
		{$,$,$,$,$,$,$,$,242,0,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$},//9 哈尔滨
		{$,$,676,$,$,$,$,$,$,$,0,511,$,842,$,$,$,$,$,$,$,$,$,$,$},//10西安
		{$,$,$,$,695,$,$,$,$,$,511,0,349,$,$,$,$,$,$,$,$,$,$,$,534},//11郑州
		{$,$,$,$,$,674,$,$,$,$,$,349,0,$,$,$,$,$,$,$,$,$,$,651,$},//12徐州
		{$,$,$,$,$,$,$,$,$,$,842,$,$,0,1100,967,$,$,$,$,$,$,$,$,$},//13成都
		{$,$,$,$,$,$,$,$,$,$,$,$,$,1100,0,639,$,$,$,$,$,$,$,$,$},//14昆明
		{$,$,$,$,$,$,$,$,$,$,$,$,$,967,639,0,$,607,902,$,$,$,$,$,$},//15贵阳
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,0,255,$,$,$,$,$,$,$},//16南宁
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,607,255,0,672,$,$,$,$,$,$},//17柳州
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,902,$,672,0,675,$,367,$,$,409},//18株州
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,675,0,140,$,$,$,$},//19广州
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,140,0,$,$,$,$},//20深圳
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,367,$,$,0,622,825,$},//21南昌
		{$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,622,0,$,$},//22福州
		{$,$,$,$,$,$,$,$,$,$,$,$,651,$,$,$,$,$,$,$,$,825,$,0,$},//23上海
		{$,$,$,$,$,$,$,$,$,$,$,534,$,$,$,$,$,$,409,$,$,$,$,$,0},//24武汉
	};	
	int v_start,v_end;//起点，终点城市
	int dist[MAXVEX]={0},path[MAXVEX]={0}, S[MAXVEX]={0};	
Labl:	
	{
		cout<<"********************************************************************************"<<endl;
		cout<<"         0  乌鲁木齐 ** 1  西宁** 2  兰州 ** 3  呼和浩特 ** 4  北  京"<<endl;
		cout<<"         5  天    津 ** 6  沈阳** 7  大连 ** 8  长    春 ** 9  哈尔滨"<<endl;
		cout<<"         10 西    安 ** 11 郑州** 12 徐州 ** 13 成    都 ** 14 昆  明"<<endl;
		cout<<"         15 贵    阳 ** 16 南宁** 17 柳州 ** 18 株    州 ** 19 广  州"<<endl;
		cout<<"         20 深    圳 ** 21 南昌** 22 福州 ** 23 上    海 ** 24 武  汉"<<endl;
		cout<<"********************************************************************************"<<endl;
		cout<<"                              请选择查询方式：               "<<endl;	
		cout<<"                  A:一站到多站    B:一站到一站   C:退出"          <<endl;	
		cout<<"********************************************************************************"<<endl;
		char flag;//选择查询类型	
		cin>>flag;
		switch(flag)
		{		
		case 'A':
	    case 'a':goto Labl_1;break;			
		case 'B':
	    case 'b':goto Labl_2;break;
		case 'C':
	    case 'c':goto end;break;
		default:goto Labl;
		}	
	}
Labl_1 :
	{		  
		cout<<"请输入起始城市的编号："<<endl;		  
		cin>>v_start;		  
		cout<<"以 ";			  
		out(v_start);		  
		cout<<"  为起始城市的交通路线为："<<endl;
		ShortPath( G,dist,path,S,v_start);
		output(dist,path,S,v_start);
		goto Labl;
	}
Labl_2:
	{
		cout<<"请输入起始城市的编号："<<endl;		  
		cin>>v_start;
		cout<<"你输入的起始城市是："<<endl;
		out(v_start);
		cout<<endl<<"请输入终点城市的编号："<<endl;
	    cin>>v_end;
		cout<<"你输入的终点城市是："<<endl;
		out(v_end);
        cout<<endl<<"以 ";	
		out(v_start);
		cout<<" 为起始城市 ";      
		out(v_end);
		cout<<" 为终点城市的交通路线为："<<endl;
		ShortPath( G,dist,path,S,v_start);
		output(dist,path,S,v_start,v_end);
		goto Labl;
	}
end:;//退出程序
}