最短路径（1）.cpp

校园导游咨询参考

//最短路径算法[DJS ALGRITEM] 
/*算法分析：
手动地把地图上的n个城市分别标成n个的数组成员v[0]~v[n-1]，铁路看成边，城
市看成顶点，构成图； 
算法中当两点间有边时，把权值赋给cost数组，无边时cost对应值置为UP(无穷)，cost
[i][i]=0;以次初始化图；
根据起点vs，把起点与各点i之间的直接距离赋给dist[i],找出其中的最小值dist[j]
此时vs->vj的最短路程和路径确定，标志位s[j]=1；再对其他s[i]=0的点i的dist
[i]做相应的修改；重复以上步骤n-1次，求出源点到各点i的最短路程dist[i]、
最短路径存入path[i].pnode[j](vs==vt时另作处理);
输出vs->vt的最短路程dist[vt],最短路径path[vt].pnode[j](j:0~path[vt].num);
 -------------------------------------------------------------------
输入、输出示例：
输入如下：
1 2         //vs=v1,vt=v2
顶点个数：5
输入各边，以0 0 0 表示结束：
      第1条边->顶点，顶点，边长：
      0 1 7
      第2条边->顶点，顶点，边长：
      0 2 2 
      第3条边->顶点，顶点，边长：
      2 3 3
      第4条边->顶点，顶点，边长：
      1 3 9
      第5条边->顶点，顶点，边长：
      3 4 4
      第6条边->顶点，顶点，边长：
      2 4 15
      第7条边->顶点，顶点，边长：
      0 0 0
输出如下：
从v1到v2的最短路径长度如下：
    （起点->终点）     最短路程         最短路径 
    -----------        --------          --------
    （vs->vt）           9             (v1,v0,v2)//从v1经v0到v2为v1->v2的最短路径
*/
#include<iostream>
using namespace std;
#define MAX 20
#define UP 10000 
int cost[MAX][MAX];
int dist[MAX],n;
struct//顶点的结构体数组
{
	int num;
	int pnode[MAX];
}path[MAX];
void creatgraph()//初始化图
{
	int i,j,s,e,len,contin=1;
	cout<<"顶点个数：";
		cin>>n;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			cost[i][j]=UP;
		cost[i][i]=0;
	}
	cout<<"输入各边，以0，0，0表示结束：\n";
	i=1;
	while(contin==1)
	{
		cout<<"\t第"<<i<<"条边->顶点，顶点，边长："<<endl;
			cin>>s>>e>>len;
		if(s==0&&e==0&&len==0)
			contin=0;
		else if(s>=0&&s<n&&e>=0&&e<n&&len>0)
		{
			cost[s][e]=len;cost[e][s]=len;
			i++;
		}
		else
			cout<<"\t\t边值错误，重新输入!\n";
	}
}
void shortdjs(int vs1,int vt1)  //求最短路径
{
	int s[MAX];
	int mindis,dis,i,j,k,u;
	for(i=0;i<n;i++)
	{ 
		dist[i]=cost[vs1][i];
		path[i].pnode[0]=vs1;
		path[i].num=0;
		s[i]=0;
    }
	s[vs1]=1;
	path[vs1].num++;
    path[vs1].pnode[path[vs1].num]=vs1;
    for(i=1;i<n;i++)
	{
		mindis=UP;
		for(j=0;j<n;j++)
			if(s[j]==0&&dist[j]<mindis)
			{
				u=j;
				mindis=dist[j];
			}
			s[u]=1;
			for(j=0;j<n;j++)
				if(s[j]==0)
				{                                  
					dis=dist[u]+cost[u][j];
					if(dist[j]>dis)
					{
						dist[j]=dis;
						for(k=0;k<=path[u].num;k++)
						{path[j].pnode[k]=path[u].pnode[k];}
						path[j].pnode[k]=u;
						path[j].num=path[u].num;
						path[j].num++;
					}                    /*如果从vs->vj还有更短路径，则修改dist[j],并把path[j].pnode[]替换成path[u].pnode[]*/ 
                    }
                path[u].num++;
                path[u].pnode[path[u].num]=u;
                }
                }
void dispath(int vs2,int vt2)  //输出最短路径
{
	int j;
	cout<<"\n  从v"<<vs2<<"到v"<<vt2<<"的最短路径长度如下:\n";
	cout<<"\t(起点->终点)  最短路程    最短路径\n";
	cout<<"\t------------   --------   -------------\n";
	cout<<"\t (vs->vt):    ";
    if(dist[vt2]<UP)
			cout<<dist[vt2]<<"      (";
	else
			cout<<"无穷       (";
			
	   for(j=0;j<path[vt2].num;j++)
	     cout<<"v"<<path[vt2].pnode[j]<<", ";
    cout<<"v"<<vt2<<")\n";//若vs==vt,则输出dist=0,path:(vs,vs) 
}
int main()//主函数
{
    int vs,vt;
    cin>>vs;
    cin>>vt;
	creatgraph();
	shortdjs(vs,vt);
	dispath(vs,vt);
	system("PAUSE");
}

/*注：本程序运行环境为Dev-C++;*/