Bellman—Ford算法的时间复杂度比较高，原因在于Bellman—Ford算法要递推n次，每次递推，扫描所有的边，在递推n次的过程中很多判断是多余的，SPFA算法是Bellman—Ford算法的一种队列实现，减少了不必要的冗余判断。
大致流程：用一个队列来进行维护。初始时将源点加入队列。每次从队列中取出一个顶点，并与所有与它相邻的顶点进行松弛，若某个相邻的顶点松弛成功，则将其入队。重复这样的过程直到队列为空时算法结束。
实现过程：（1）取出队列头顶点v，扫描从顶点v发出的每条边，设每条边的终点为u，边<v,u>的权值为w，如果dist[v]+w<dist[u],则dist[u]=dist[v]+w,修改path[u]为v，若顶点u不在队列当中，还要将u入队列；如果dist[v]+w<dist[u],则对顶点u不做任何处理。（代码中u为起点，v为终点，这点不同）。
（2）重复执行上述过程直至队列为空。
上面看起来好抽象，举个栗子吧：
假设顶点3在队列中，取出顶点3，这时有个问题？从源点经过顶点3 到3的邻接点2和5的距离是否比之前更短呢？可能的情况：
dist[3]+w(3,2), dist[3]+w(3,5)分别和dist[2]与dist[5]进行比较，如果更短的话，则更新dist[2],dist[5]。如果被更新且不在队列中，则要入队。
例题：求顶点0到其他各顶点的最短路径长度，并输出相应的最短路径
测试数据：
输入：
7 0 1 6 0 2 5 0 3 5 1 4 -1 2 1 -2 2 4 1 3 2 -2 3 5 -1 4 6 3 5 6 3 -1 -1 -1
输出：
1 0-3-2-1
3 0-3-2
5 0-3
0 0-3-2-1-4
4 0-3-5
3 0-3-2-1-4-6
#include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std; #define INF 999999 #define MAXN 110 struct ArcNode { int to; int weight; ArcNode *next; }; queue<int>Q; int n; ArcNode *List[MAXN];///定义了一大堆只能存放结点地址的指针，用来当做边链表的表头指针 int inq[MAXN]; int dist[MAXN],path[MAXN]; void SPFA(int src)///求源点src到其他各点的最路径长度 { int i,u; ArcNode *temp; for(i=0;i<n;i++)///初始化 { dist[i]=INF; ///距离源点距离都为无穷 path[i]=src; ///所有顶点都假设与v0有直接路径 inq[i]=0; ///都不在队列，为0 } dist[src]=0;path[src]=src; inq[src]++;///将src加入队列 Q.push(src); while(!Q.empty()) { u=Q.front(); Q.pop(); inq[u]--;///头结点出队 temp=List[u];///temp等于编号为u的变量表的头结点 while(temp!=NULL) { int v=temp->to; if(dist[u]+temp->weight<dist[v]) { dist[v]=dist[u]+temp->weight; path[v]=u;///更新dist和path if(!inq[v]) { Q.push(v); inq[v]++; }///如果顶点v不在队列中，入队 } temp=temp->next; } } } int main() { int i,j; int u,v,w; scanf("%d",&n); memset(List,0,sizeof(List)); ArcNode *temp; while(1) { scanf("%d%d%d",&u,&v,&w); if(u==-1&&v==-1&&w==-1) break; temp=new ArcNode; temp->to=v; temp->weight=w; temp->next=NULL; if(List[u]==NULL) List[u]=temp;///头插法构造边链表 else { temp->next=List[u]; List[u]=temp; } } SPFA(0);///求顶点0到其他各点的最短路径 for(j=0;j<n;j++)///释放边链表上各边结点所占的空间 { temp=List[j]; while(temp!=NULL) { List[u]=temp->next;///存储下一个 delete temp;///删除这一个 temp=List[u];///定位下一个 } } int shortest[MAXN]; for(i=1;i<n;i++) ///倒向追踪法输出路径，奇妙 { printf("%d\t",dist[i]); memset(shortest,0,sizeof(shortest)); int k=0; shortest[k]=i; while(path[shortest[k]]!=0) { k++; shortest[k]=path[shortest[k-1]]; } k++; shortest[k]=0; for(j=k;j>0;j--) printf("%d->",shortest[j]); printf("%d\n",shortest[0]); } return 0; } /* /* 测试数据： 输入： 7 0 1 6 0 2 5 0 3 5 1 4 -1 2 1 -2 2 4 1 3 2 -2 3 5 -1 4 6 3 5 6 3 -1 -1 -1 输出： 1 0->3->2->1 3 0->3->2 5 0->3 0 0->3->2->1->4 4 0->3->5 3 0->3->2->1->4->6 */
