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)