cpp1.cpp

最短路径的课程设计

#include <iostream.h>
#define INF 32767
#include<iomanip.h>
#include<stdlib.h>
const  int maxvex=100;
//单源最短路径
void dijkstra(int cost[][maxvex],int n,int v)
{
	int ds[maxvex],p[maxvex];
	int s[maxvex];
	int min,i,j,u,w;
	for (i=0;i<n;i++)
	{
		ds[i]=cost[v][i];//距离初始化
		s[i]=0;        //S[ ]置空
		if (cost[v][i]<INF)//路径初始化
			p[i]=v;
		else
			p[i]=-1;
	}
	s[v]=1;p[v]=0;//源点编号 V放入S中
	for (i=0;i<n;i++)//循环直到所有顶点的最短路径都求出
	{
		min=INF;
		u=-1;
		for (j=0;j<n;j++)//选取不在S中且具有最小距离的顶点U
			if(s[j]==0&&ds[j]<min)
			{
				u=j;
				min=ds[j];
			}
			if (u!=-1)//找到最小距离的顶点U
			{
				s[u]=1;//将顶点U加入S中
				for (j=0;j<n;j++)//修改不在S中的顶点的距离
					if (s[j]==0)
						if (cost[u][j]<INF &&ds[u]+cost[u][j]<ds[j])
						{
							ds[j]=ds[u]+cost[u][j];
							p[j]=u;
						}
			}
	}
	cout<<setw(2)<<"\n 单源最短路径:\n";
	for (i=0;i<n;i++)//输出最短路径的长度,路径逆序输出
	{
		if (i!=v)
		{
			cout<<""<<v<<"->"<<i<<":";
			if (s[i]==1)
			{
				cout<<setw(2)<<"路径长度为"<<setw(2)<<ds[i]<<"";
				w=i;
				cout<<setw(2)<<"路径逆序为";
				while(w!=v)//一直加溯到初始顶点
				{
					cout<<w<<",";
					w=p[w];
				}
				cout<<w<<endl;
			}
			else
				cout<<setw(2)<<"不存在路径"<<endl;
		}
	}
}//单目标
void danmubiao(int cost[][maxvex],int v,int n)
{
	int ds[maxvex],p[maxvex];
	int s[maxvex];
	int min,i,j,u,w;
	for (i=0;i<n;i++)
	{
		ds[i]=cost[v][i];  //距离初始化
		s[i]=0;          //S[ ]置空
		if (cost[v][i]<INF)//路径初始化
			p[i]=v;
		else
			p[i]=-1;
	}
	s[v]=1;p[v]=0; //源点编号 V放入S中
	for (i=0;i<n;i++) //循环直到所有顶点的最短路径都求出
	{
		min=INF;
		u=-1;
		for (j=0;j<n;j++)
			if(s[j]==0&&ds[j]<min) //选取不在S中且具有最小距离的顶点U
			{
				u=j;
				min=ds[j];
			}
			if (u!=-1) //找到最小距离的顶点U
			{
				s[u]=1; //将顶点U加入S中
				for (j=0;j<n;j++)//修改不在S中的顶点的距离
					if (s[j]==0)
						if (cost[u][j]<INF &&ds[u]+cost[u][j]<ds[j])
						{
							ds[j]=ds[u]+cost[u][j];
							p[j]=u;
						}
			}
	}
	cout<<setw(2)<<"\n 单目标最短路径:\n";
	for (i=0;i<n;i++)//输出最短路径的长度,路径逆序输出
	{
		if (i!=v)
		{
			cout<<""<<i<<"->"<<v<<":";
			if (s[i]==1)
			{
				cout<<setw(2)<<"路径长度为"<<setw(2)<<ds[i]<<"";
				w=i;
				cout<<setw(2)<<"路径顺序为";
				while(w!=v) //一直加溯到初始顶点
				{
					cout<<w<<",";
					w=p[w];
				}
				cout<<w<<endl;
			}
			else
				cout<<"不存在路径"<<endl;
		}
	}
}

//单顶点
void dandingdian(int cost[][maxvex],int a,int b)
{
	int G[maxvex][maxvex],p[maxvex][maxvex];
    int i,j,k,w;
	for (i=0;i<6;i++)     //置初值
		for (j=0;j<6;j++)
		{
			G[i][j]=cost[i][j];
			p[i][j]=-1;
		}
		for (k=0;k<0;k++)
		{
			for (i=0;i<6;i++)
				for (j=0;j<6;j++)
					if (G[i][j]>G[i][k]+G[k][j])
					{
						G[i][j]=G[i][k]+G[k][j];
						p[i][j]=k;
					}
		}
    if(a!=b)
	{
        cout<<setw(2)<<""<<a<<"->"<<b<<":";
		if (G[a][b]==INF)
		{
		  if(a!=b)
		  cout<<setw(2)<<"不存在路径"<<endl;
		} 
       else
	   { cout<<setw(2)<<"路径长度为"<<setw(3)<<G[a][b]<<"";
         cout<<setw(2)<<"路径为"<<a<<"";
         w=p[a][b];
         while (w!=-1)
		 {
	      cout<<w<<"";
	      w=p[w][b];
		 }
       cout<<b<<endl;
	   }
	}
}
//所有顶点对间
void floyed(int cost[][maxvex],int n)
{
	int G[maxvex][maxvex],p[maxvex][maxvex];
    int i,j,k,w;
	for (i=0;i<n;i++)//置初值
		for (j=0;j<n;j++)
		{
			G[i][j]=cost[i][j];
			p[i][j]=-1;
		}
		for (k=0;k<n;k++)
		{
			for (i=0;i<n;i++)
				for (j=0;j<n;j++)
					if (G[i][j]>G[i][k]+G[k][j])
					{
						G[i][j]=G[i][k]+G[k][j];
						p[i][j]=k;
					}
		}
cout<<setw(2)<<"\n 所有顶点对间最短路径:\n";
for (i=0;i<n;i++)/*输出最短路径*/
    for (j=0;j<n;j++)
       if(i!=j)
	   {
		   cout<<""<<i<<"->"<<j<<":";
		   if (G[i][j]==INF)
		   {
			   if(i!=j)
				   cout<<setw(2)<<"不存在路径"<<endl;
		   }
		   else
		   {
			   cout<<setw(2)<<"路径长度为"<<setw(3)<<G[i][j]<<" ";
			   cout<<setw(2)<<"路径为"<<i<<" ";
			   w=p[i][j];
			   while (w!=-1)
			   {
				   cout<<w<<" ";
				   w=p[w][j];
			   }
			   cout<<j<<endl;
		   }
	   }
}
void main()
{
	int cost[6][maxvex]={
		      {0,10,30, INF,INF,INF},
		      {INF,0,20,INF,INF,INF},
		      {INF,15,0,15,INF,INF },
		      {5,INF,INF,0,20,INF},
		      {20,INF,INF,INF,0,50},
		      {INF,INF,INF,25,15,0}};
		cout<<"           最短路径          "<<endl;
		cout<<"         ============        "<<endl;
		cout<<"       1.单源最短路径        "<<endl;
		cout<<"       2.单目标最短路径      "<<endl;
		cout<<"       3.单顶点对间最短路径  "<<endl;
		cout<<"       4.所有顶点对间最短路径"<<endl;
		cout<<"       请选择(1~4,0: 退出)   ";
		int x;
		cin>>x;
		if (x==0) exit(0);
		else if	(x==1) 
		{
			int a1;
			cout<<"   输入单源点：";
			cin>>a1;
			dijkstra(cost,6,a1);
		}//单源
		else if (x==2) 
		{
			int a2;
			cout<<"   输入单目标点:";
			cin>>a2;
			danmubiao(cost,a2,6);
		}//单目标
		else if (x==3) 
		{
			int a,b;
			cout<<"   输入两个顶点:";
		    cin>>a>>b;
		    dandingdian(cost,a,b);//单顶点对间
		}
		else if(x==4) floyed(cost,6);//所有顶点对间
}