|
|
| |
|
| |
| |
| Dijkstra算法 |
|
[ 2008-9-16 19:15:00 | By: wantnon ] |
1,将起点加入S;
2,S中新加顶点冲洗其所有后继(Min);
找S外顶点中累积值最小者v;
如果v累积值有限,将v加入S,返回2。
如果v累积值为无穷,无路径,退出;
如果终点已加入S,终止。
结果：S中各点的累积值即为其到起点的最短路径长。
注：
1，S保持其中顶点累积值已达终态。
2，另设一数组追踪路径即可。
C++程序：
＃i nclude<iostream.h>
ShortestPath (double weivvmat[][MAXNL+1],int Nv,int st,int ed)
{
int i,j;
bool S[MAXNL+1]={false};//记录顶点是否已加入(S[i]==true则i点已加入)
int sumD[MAXNL+1];//各顶点的累积量
for(i=1;i<=Nv;i++)sumD[i]=INF;//sumD初始化
int foev[MAXNL+1]={0};//各点前驱
S[st]=true;//加入起点
sumD[st]=0;//起点累积量为0
int LsAddV=st;//存新加入的顶点
while(1)
{
//用新加入S的冲一次
for(i=1;i<=Nv;i++)//搜索所有顶点i
{
if(weivvmat[LsAddV][i]!=INF//如果i是LsAddV的邻接点
&&!S[i]//i不在S中(这个条件可有可无)
&&sumD[LsAddV]+weivvmat[LsAddV][i]<sumD[i])//且i经LsAddV累积量更小
{//更新点i的累积量
sumD[i]=sumD[LsAddV]+weivvmat[LsAddV][i];
//更新foev
foev[i]=LsAddV;
}
}
//找S外围点中累积量最小的点
int min=INF;//S外围点的最小累积量
int minv=0;//S外围点中累积量最小的点
for(i=1;i<=Nv;i++)//搜索所有顶点i
{
if(!S[i]//如果i不在S中
&&sumD[i]<min)//且i的累积量更小
{
min=sumD[i];
minv=i;
}
}
if(minv==0)
{
cout<<"错误:路径不通!"<<endl;
exit(1);
}
//minv加入S
S[minv]=true;
LsAddV=minv;
//如果终点已加入，终止
if(S[ed]==true)break;
}
//输出路径
int p=ed;
while(p!=0)
{
cout<<p<<"("<<sumD[p]<<")"<<"←";
p=foev[p];
}
cout<<endl;
}
|
|
| | |
|
