V:原始图中的顶点集合
S:存放已求得最短路径的顶点的集合
1.初始状态时,集合S中只有一个源点v0。首先产生从源点v0到它自身的路径,其长度为0,将v0加入S。
2.计算v0到V-S中的各顶点vi的当前最短路径(即为v0直接到达vi或者间接经过S中的顶点到达vi的最短路径),选取长度最短的路径作为下一条最短路径,并将该路径的终点vi 属于V-S加入S。
3.重复步骤2,直到S=V时算法结束。
当前最短路径 在算法执行中,一个顶点vi 属于V-S的当前最短路径,是一条从源点v0到顶点vi的路径(v0,....,u, vi )且满足在该路径上,除顶点vi 外,其余顶点的最短路径都已求得,即路径(v0,?,u)上所有顶点都属于S。(v0,.....,u,vi )是所有这些路径中的最短者。
选择数据结构
一维数组d
d[i]中存放从源点v0到i的当前最短路径的长度,该路径上除顶点i自身外,其余顶点都属于S,并且这是所有这些路径中的最短者。
一维整型数组path
path[i]给出从v0到顶点i的最短路径上,位于顶点i前面的那个顶点。例如,从v0到v1的最短路径为
(v0,v2,v3,v1)则有path[1]=3,path[3]=2,path[2]=0
一维布尔数组s
若s[i]为true,表示顶点i在S中,否则表示i在V-S中。
c++实现
template <class T>
int ExtMGraph<T>::Choose(int* d, bool* s)
{
int i,minpos; T min;
min=INFTY; minpos=-1;
for (i=1;i<n;i++)
if (d[i]<min &&!s[i]){
min=d[i];minpos=i;
}
return minpos;
}
template <class T>
void ExtMGraph<T>::
Dijkstra(int v,T* d,int* path)
{
int i,k,w;
if (v<0||v>n-1)
cout<< “OutOfBounds”;return;
bool *s=new bool[n];
for (i=0;i<n;i++){
s[i]=false;
d[i]=a[v][i];
if (i!=v && d[i]<INFTY) path[i]=v;
else path[i]=-1;
}
s[v]=true; d[v]=0;
for (i=1;i<n-1;i++){
k=Choose(d,s);
s[k]=true;
for (w=0; w<n; w++) //更新d和path
if (!s[w] && d[k]+a[k][w]< d[w]){
d[w]=d[k]+a[k][w];
path[w]=k;
}
}
}
关键步骤图解
执行过程
上述算法的执行时间为O(n2)。如果人们只希望求从源点到某一个特定顶点之间的最短路径,也需要与求单源最短路径相同的时间复杂度O(n2)