最短路径算法.cpp

共有10个文件代码

#include<iostream.h>
#define M 20  //最多顶点个数
#define up 10000 //定义一个无穷大的值
int cost[M][M] ; //带权的邻接矩阵
int dist[M],n; //dist为v0到各顶点的最短路程
struct
{
	int num;
	int pnode[M];
}path[M];  //path为从v0到各顶点的最短路径
void creatgraph()   //创建带权无向图
{
	int i,j,s,e,len,contin=1;//s-顶点号,e-顶点号,len-权值
	cout<<"顶点个数 ";
	cin>>n;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			cost[i][j]=cost[j][i]=up;
		cost[i][i]=0;
	}
	cout<<"输入各边(以0，0，0表示结束): "<<endl;;
	i=1;
	while (contin==1)
	{
		cout<<" 第"<<i<<"条边-顶点，顶点，权值";
		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;
			i++;
		}
		else
			cout<<"信息输入错误，请重新输入";
	}

}
void shortdjs() //求最短路径
{
	int s[M];
	int mindis,dis,i,j,v0=0,u;
	for(i=0;i<n;i++)
	{
		dist[i]=cost[v0][i];
		path[i].pnode[0]=v0;
		path[i].num=0;
		s[i]=0;
	}
	s[v0]=1;
	for(i=1;i<n;i++)
	{
		mindis=up;
		for(j=1;i<n;i++)
	     if(s[j]==0 && dist[j]<mindis)
		 {
			 u=j;
			 mindis=dist[j];
		 }
	s[u]=1;
	for(j=1;j<n;j++)
		if(s[j]==0)
		{
			dis=dist[u]+cost[u][j];
			if(dist[j]>dis)
			{
				dist[j]=dis;
				path[j].num++;
				path[j].pnode[path[j].num]=u;
			}
		}
     path[i].num++;  //将终点i添加到路径中
     path[i].pnode[path[i].num]=i;
	}
}
void dispath() //输出最短路径
{
	int i,j;
	cout<<" 从v0到各顶点的最短路径长度如下：";
	cout<<endl;
	cout<<" (起点->终点) 最短长度  最短路径 ";
	cout<<endl;
	for(i=1;i<n;i++)
	{
		cout<<" (v0->v"<<i<<"):  ";
		if(dist[i]<up)
		   cout<<dist[i]<<" (";
	else 
		cout<<" 无穷大 (";
	for(j=0;j<path[i].num;j++)
		cout<<"v"<<path[i].pnode[j]<<", " ;
		cout<<"v"<<path[i].pnode[path[i].num]<<") "<<endl;
	}
}
void main()
{
	creatgraph();
	shortdjs();
	dispath();
}