【算法赌场】SPFA算法

1.算法简介

SPFA 算法的全称是：Shortest Path Faster Algorithm，是西南交通大学 段凡丁 于 1994 年发表的论文中的名字。不过，段凡丁的证明是错误的，且在 Bellman-Ford 算法提出后不久（1957 年）已有队列优化内容，所以国际上不承认 SPFA 算法是段凡丁提出的。

这个事情其实给我们信息学的学习一些启发的。首先，段凡丁肯定是一个大神了，他整理出了这个算法，发表论文。本身，他这篇论文质量很高的，这个算法本身没毛病，问题是作为一个论文，要把一个事情的来龙去脉都说得很清楚很严谨，不仅仅是这段代码能跑成功，而且还要有一个详细的证明过程，证明这段代码运行的结果是正确的，对各种情况进行分析和估算。段凡丁就是在论证这个算法的计算复杂度的时候出现了错误，所以，国际上不怎么承认段凡丁是 SPFA 算法的提出者（逻辑就是你连讲都没讲透彻，这怎么能说就是你的研究成果呢？）。

大家回头想想，如果你学一个算法，要滴水不漏的理解透彻，能讲得出这个算法为什么是对的，是多么呢？人家段大神都在这个问题上栽了大跟斗的。如果你真的要那么做，你一定要找人家的学术论文来看，每一字句去推敲。这个事，就不是我们课堂上那一丁点时间能解决的。所以，从初中开始，大家学习信息学，很多东西就是理解个 7-8 成之后拿来用，你可以有一套自己的思维导图，大致能想明白这个算法为啥是对的，但是，距离严谨证明是有差距的，但能用就行。

2.算法步骤

SPFA 其实是 Bellman-Ford 算法的一个改进。如果仅仅从代码角度来看，两个算法差异很大的，但是，从其思想来看同出一脉。

我们之前说过，Bellman-Ford 算法是有 BFS 算法的影子的，通过 N-1 轮松弛（第一层循环），找到最短路径。因为 N 个顶点的图，最长的简单路径不应该超过 N-1。Bellman-Ford 算法里面的第一层循环就是步数。

既然如此，为了提高效率，我们应该基础每一轮松弛了哪一些点，下一轮，就从这些新点往外延伸去松弛新的点。如果一个点在第 i 轮没有被松弛，我们在第 i-1 轮就不应该试图从它出发去找新的可到达点。这就是 SPFA 算法的核心所在。

为了区分哪一些点是新找到的点，就需要通过一个队列来做控制，新找到的点进队列，一个点往外延伸（类似搜索、探路）了之后，就把他弹出队列。一直重复这个操作，直到队列为空，SPFA 过程就结束了。

struct Edge{ //边的结构体，出发点不需要存，因为边是棣属于顶点的
	int v,w;
}e[500001];

int dis[10001]; 
vector <int> chi[10001];
queue <int> q; 

bool inque[10001];

void SPFA(){
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	inque[s] = true; // inque 数组是用来记录这个顶点是否在队列当中
	q.push(s);


	while(q.size())
	{
		int u=q.front();
		q.pop();
		inque[u] = false;
		for(int i=0;i<chi[u].size();i++) //从顶点 t 出发，试图松弛一些点
		{
            // chi[u] 是动态数组，存放了从顶点 u 出发的所有边
			Edge tmp_e = e[chi[u][i]];  //chi[u][i] 是边的 id
			int v = tmp_e.v; // 这条边是从 u 到 v
			if(dis[v]>dis[u]+tmp_e.w) //松弛 ee.v 这个顶点，从 s 到 u，再从 u 到 v 是一条更优的路径
			{
				dis[v]=dis[u]+tmp_e.w;
				//v 是新探索到的顶点，放入队列
                if(!vis[v]){
					q.push(v);
					inque[v] = true;
				}
			}
		}
	}
}