l7_9.cpp

《数据结构（C++描述）》-李根强-源代码

//用迪杰斯特拉算法求单源点的最短路径
#include<iostream.h>
const int max=32767;
const   int   n=5;      //max表示图中顶点的个数
const int e=9;
struct   Graph
{  
int  arcs [n+1][n+1];           //图的邻接矩阵
int dist [n+1] ;                //存放从源点到各顶点的最短路径
int path [n+1] ;             //存放在最短路径上该顶点的前一顶点号
int s[n+1];                  //已求得的在最短路径上的顶点的顶点号
}g;
void  shortestpath (const int Vl)     //Vl为源点
{for (int i=1;i<=n;i++)
{g.dist[i]=g.arcs[Vl][i];
g.s[i]=0;                         //已求出最短路径上的顶点集合初始化
if ((i!=Vl)&&(g.dist[i]<max)) g.path[i]=Vl;
else  g.path[i]=0;
}
g.s[Vl]=1; g.dist[Vl]=0;
for (i=1; i<n; i++)
{ int min=max; int u=Vl;
for (int j=1; j<=n;j++)                       //求最短路径
if (!g.s[j]&& g.dist[j]<min) {u=j,min=g.dist[j];}
g.s[u]=1;                                              // 将距离值最小的顶点并入集合S中
for(int w=1; w<=n; w++)              //修改路径长度
if ((!g.s[w])&&(g.arcs[u][w]<max) &&(g.dist[u]+g.arcs[u][w]<
g.dist[w])) {g.dist[w]=g.dist[u]+g.arcs[u][w]; g.path[w]=u;} 
}
for (i=1;i<=n;i++)                    //输出路径长度及路径
{if (i!=Vl)
{cout<<"最短距离为："<<g.dist[i]<<"   ";                             
cout<<"经过的顶点为："<<i;                                    //输出终点
int pre=g.path[i];
while (pre!=0)
{cout<<"←"<<pre;
 pre=g.path[pre];
}
cout<<endl;
}
}
}
void main( )
{ int i,j,w,k;
  for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++)
		  if(i==j) g.arcs[i][j]=0;
		  else g.arcs[i][j]=max;
	for(k=1;k<=e;k++)
    { cout<<"请输入一条边及权值:";
	  cin>>i>>j>>w;
	  cout<<endl;
	  g.arcs[i][j]=w;
	}
	cout<<"请输入源点：";
	cin>>i;
	cout<<endl;
	cout<<"从"<<i<<"出发的最短路径为"<<endl;
	shortestpath(i);
}