zz http://blog.sina.com.cn/s/blog_6ad20aef0100mc1a.html
Spfa算法 （模板源代码）
这是Bellman Ford的改进算法。
算法介绍：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
时间复杂度：期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
通用模板设计（源代码）：
先说明一下，g所求有向图（g[i][j]为i到j的边长度，如果g[i][j]不存在，则赋值为-1），Q为队列，dis中所有元素应初始化为inf(0xfffffff最大值),visit中所有元素应初始化为false。
void spfa(int s,int m)
{
int i,k,ts=0,te=1;
Q[ts] = s;
dis[s] = 0;
while(ts<te)
{
k = Q[ts];
visit[k]=false; //修改后增加的 2010.8.18 01:27
for(i=1;i<=m;i++)
{
if(g[k][i]>0 && dis[i] - g[k][i] > dis[k])
{
dis[i] = dis[k] + g[k][i];
if(!visit[i])
{
Q[te++] = i;
visit[i] = true;
}
}
}
ts++;
}
}
其中，得到的dis数组dis[i]就是的源点s到点i的最短路径长度。
值得一提的是，当所求图的点很多时，用二维数组来储存图可能会MLE，这就需要用邻接表或者邻接矩阵来储存图了，只要将该模板稍改一下，就可以用了。不过，学会该算法的思想是最重要的了！