单源最短路径的Dijkstra算法

单源最短路径的Dijkstra算法

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
2、在上述的最短路径dist[]中选一条最短的，并将其终点（即）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的所有顶点。 SPFA实际上是Bellman-Ford基础上的队列优化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每条边(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
dequedq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i{
to=adjmap[x][i].to;
if((dist[x]dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}