SPFA算法理论体系终极论证
SPFA算法理论体系终极论证
SPFA（Shortest Path Faster Algorithm）算法是一种用于求解带负权边的图的单源最短路径问题的算法。本文将从历史背景、理论基础、算法实现、复杂度分析等多个方面，对SPFA算法进行全面的探讨和论证。
历史事件
SPFA算法是对Bellman-Ford算法的一种优化。虽然国内普遍认为SPFA算法首次提出是在1994年西南交通大学段凡丁的论文中，但实际上，早在1956年Bellman-Ford算法提出时就已经包含了类似bfs的队列方式松弛的思想。段凡丁的贡献主要在于给这种算法起了一个名字，但他的论文存在很多漏洞，且思考较为简单，因此并未得到学术界的广泛认可。国内首次清晰正确地提出SPFA算法的是2009年中山纪念中学的姜同学，但他的论文由于作者年龄和经验的限制，写得不够成熟。目前，华东师大可信实验室的SPFA论文被认为是写得最为严谨的。
Bellman-Ford算法简述和证明
Bellman-Ford算法是SPFA算法的理论基础。其核心思想是：在一个有n个点、m条边的图中，每个边最多被松弛n-1次，否则说明图中存在负权环。
以下是Bellman-Ford算法的代码实现：
int Bellman_Ford(int x){
for(int i=1;i<=n;i++){dist[i]=oo;}
dist[x]=0;
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++)
if(dist[e[j].y]>dist[e[j].x]+e[j].w)
dist[e[j].y]=dist[e[j].x]+e[j].w;
}
for(int j=1;j<=m;j++)
if(dist[e[j].y]>dist[e[j].x]+e[j].w)return -1;
return 1;
}
算法正确性证明
证明每个边最多被松弛n-1次，否则有负权环：
- 首先源点在0轮就已经确定了(最短路直接是0)，所以len=0时，0轮确定。
- 如果第i轮松弛确定了path上y点的最短路path_y，path_y点数len(path_y)=i。那么根据上面的代码，对path上的y下一个点x，edge(x,y)在第i+1轮一定会被做松弛判断。所以x的最短路在第i+1轮一定被搜到，且len(path_x)=i+1。
- 所以一个边数为l的最短路，在l轮松弛后一定会被搜到。
- 而所有最短路经过的边数最多n-1,所以算法是对的。
- 如果n-1轮松弛后还边能松弛，那说明最短路经过的边数是无限的，有负权环。
这种算法虽然复杂度是O(nm)比迪杰斯特拉慢，但是可以跑有负权边的图，还能判断负环。
SPFA的正确代码
SPFA算法和Bellman-Ford算法原理相同，只是有条理地改变了松弛顺序。每次从队头取个点，松弛它的相邻点。每个点被松弛(重新进队)的次数至多是源点到它的最短路的边数，证明方法还是数学归纳法，和上面的Bellman-Ford没啥区别。
一旦发现哪个点松弛到了n次，就说明有负环。
以下是SPFA算法的正确代码实现：
int spfa(int x){
for(int i=1;i<=n;i++){dist[i]=oo;inq[i]=0;}
dist[x]=0;
int head=1,tail=0;
q[++tail]=x;
inq[s]=1;
while(head<=tail){
int cur=q[head];
int sz=con[cur].size();
for(int i=0;i<sz;i++){
edge NE=e[con[cur][i]];
if(dist[NE.x]+NE.w<dist[NE.y]){
dist[NE.y]=dist[NE.x]+NE.w;
cunt[NE.y]++;
if(cunt[NE.y]>=n)return -1;
if(!inq[NE.y]){
q[++tail]=NE.y;inq[NE.y]=1;
}
}
}
head++;
inq[cur]=0;
}
return 1;
}
段凡丁的贡献
段凡丁的论文理论根基都是不对的。段凡丁的SPFA算法并没有判负环的机制。有负环就停不下来了。再看看段凡丁对于SPFA正确性的证明。段凡丁论文里的SPFA正确性证明分成两部分：一定能找到最短路；还有算法能在有限次后收敛在最短路这两部分。
作者给出的这个正确性证明就他的算法来说是正确的。这给了后人很大的启发，他做的事情是极其重要的，尽管他并没有想的足够深入。先不提他错误的复杂度，从他的代码和证明来看，他当时并没有想到每个点至多入队n-1次，没有想到负环的情况。所以他的代码在有负环时就停不下来了。再来看看他“硬核”的复杂度分析：
这个就是作者主观臆断了。凭一堆实验就强行断定复杂度，而没有理论支撑，显然是不行的。可以构造图，把SPFA的复杂度卡成O(nm)。到这里段老师写论文的心态大概是：段老师读了一些图论的论文，受到一些启发，总结可以跑负权图的单源最短路算法，取名SPFA。然后复杂度有些精妙不太好理论分析，做了大量随机（至少没有针对性）实验后就主观断定复杂度O(m)，这是理论最好复杂度。所以兴奋地认为找到了比迪杰斯特拉跑的还快，适用范围还更广的算法。所以就写了这篇论文。但不可否认的是，这给后来的中国学者提供了宝贵的经验，在1994年是难能可贵的。
正确复杂度分析
实际上，SPFA算法的最坏复杂度是θ(nm)的。
算法复杂度是O(nm)很好理解，因为根据算法，每次取队头判断松弛的次数最多是n-1=O(n)。最多去多少次队头呢？这就是队列的累计总长度。最坏的是：每个点被他所有入度都松弛一次而入队，这样队列长度最大一共m。所以O(nm)是成立的。实际上现实中这两种最大情况不会发生。
下面构造最坏的情况，使得复杂度是θ(nm)：
这个图构造方法：
源点是1。
i到i+1有长度1的边。
1到i(3<=i<=n)分别有2*i+1的边。
i（3=<i<=n）到 j（1<=j<=i-2）有+oo的边。
所以模拟算法过程，首先i会被直接与源点相连那条边搜到，然后就是前面的点i-1出队一次，i被松弛入队一次。所以：numPop(i)=numPop(i-1)+1,numPop(1)=1
所以从1~n每个点的出队次数是：
1,2,3,4,...,i,...,n
每次出队会扫描一遍出度，1~n的出度依次是：
n-1,1,2,3,...,(i-1),...n-2,n-2
所以总判断松弛次数是
T = ∑i=1n(i−1)∗iT=\sum_{i=1}^{n}(i-1)*iT=i=1∑n (i−1)∗i
注：严格按上面的规律求出的结果和上面求和公式有O(n)级别的差值(有头尾特殊的几个和别的规律不太一样)，不影响复杂度计算，忽略不计了。
T = ∑i=1n(i−1)∗i=∑i=1ni∗i−∑i=1ni=n(n+1)(2n+1)6−n(n+1)2=θ(n3)T=\sum_{i=1}^{n}(i-1)i=\sum_{i=1}^{n}ii-\sum_{i=1}^{n}i\=\\frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}=θ(n^3)T=i=1∑n (i−1)∗i=i=1∑n i∗i−i=1∑n i=6n(n+1)(2n+1) −2n(n+1) =θ(n3)
而这个图里m是O(n2)的。所以复杂度是θ(mn)的。
另外，SPFA实际跑起来不一定比Bellman-Ford快。一道题的比较。我随便找了到最短路的题写了一发，结果如下：
SPFA的时间：
Bellman-Ford的时间：
整体来看两者差不多，但是Bellman-Ford好像快一些。。。
以上就是我知道的所有的内容了。