单源最短路径的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;

}