最短路径与最小生成树.doc

给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。
具体步骤是:1、选一顶点v为源点,并视从源点v出发的所有边为到各顶点的最短路径(确定数据结构:因为求的是最短路径,所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时,dist是源点v到顶点i的直接边长度,即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点)。2、在上述的最短路径dist[]中选一条最短的,并将其终点(即<v,k>)k加入到集合s中。3、调整T中各顶点到源点v的最短路径。因为当顶点k加入到集合s中后,源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j],取其中的较小者。4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中,再回去到第三步,如此重复,直到集合S中的包含图G的所有顶点。
实验代码如下:
#include <iostream>
using namespace std;
#define max 10000
void yuan(int n,int **a,int m)
{
int *b=new int[n+1],*s=new int[n+1];
int i,j;
for(i=1;i<=n;i++)
{
b[i]=a[m][i];s[i]=0;
}
s[m]=1;
for(int ii=1;ii<n;ii++)
{
int min=max,w=1;
for(int k=1;k<=n;k++)
if(min>b[k]&&(!s[k]))
{
w=k;min=b[k];
}
s[w]=1;
for(i=1;i<=n;i++)
if(!s[i])
{
if(b[i]>b[w]+a[w][i])
b[i]=b[w]+a[w][i];
}
}
for(j=1;j<=n;j++)
if(j!=m)
cout<<m<<"-->"<<j<<" : "<<b[j]<<endl;
}
int main()
{
int n,m,**a,i,j;
while(cin>>n>>m)
{
a=new int*[n+1];
for(i=0;i<=n;i++)
a[i]=new int[n+1];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>a[i][j];
yuan(n,a,m);
}
return 0;

}
从得到的结果上分析,固定点的位置是从2开始遍历的,2到1的最短路径是32