《算法》C++代码 SPFA
浏览数：17 /
时间：2015年06月08日
SPFA的全称是Shortest Path Faster Algorithm，一看名称八成就是中国人起的名字，因为外国人起算法名称一般都会写上自己的名字，很少谦虚。实际上，这是西南交通大学段凡丁同学于1994年发表的，是针对Bellman-Ford算法的改进。在此不过多介绍背景，直接介绍SPFA算法。
这个是单源最短路算法，效率很高，和Dijkstra二分天下。时间复杂度的分析，暂时我还没做，先摘抄2009年OI国家集训队广东中山纪念中学的姜碧野学长一篇论文中的分析：
在一般情况，SPFA的效率很高，可以证明SPFA的期望复杂度为O(KM)，K<2。但由于证明还不够严谨且适用性不广(存在针对性数据)，在此不再赘述。但将会在随后的测试中用实际数据来验证SPFA的高效性。
注：上文中所说M表示图中的边数。
其实算法思想很简单。假设起点叫S，终点叫T。用(u,v)表示边u->v的长度。依旧用d[i]表示S->i的最短路径。我们采用“松弛操作”，不断更新可以更新的d，最终无法更新终止。算法如下：
1 d ← ∞，队列Q初始化为空 2 d[S]=0，Q.in(S) 3 while(!Q.empty()) 4 { 5 u=Q.out(); 6 for(所有的边u->v) 7 if(d[v]>d[u]+(u,v)) 8 { 9 d[v]=d[u]+(u,v); 10 if(v不在队内) Q.in(v); 11 } 12 }
算法伪代码至此完毕，SPFA就是如此简洁。实际代码不予赘述。
在此多说一句，假设图中有N个点，而在SPFA过程中发现有一个点入过队N次，并且还要入队第N+1次，那么就说明图中有负环。
暂时就写到这里吧，有时间再补充。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
