最短路问题

就是求图中一源点到其他点的最短路径。（也可能为所有点到其他点的最短路径）

算法

Floyd 算法

待补充……

Bellman-Ford 算法

一种基于松弛（relax）操作的最短路算法。

一般不会写，了解就行，要用主要还是用SPFA。

以下都基于有最短路情况讨论（即没有负环）。

符号定义

• $N$——节点个数
• $M$——边个数
• $S$——源点
• $dist[v]$——源点$S$到点$v$的当前距离
• $ralax(u,v)$——以$u$为中继点，判断经过此中继点到点$v$的距离是否更短，如是则覆盖$dist[v]$

操作

1. 先对dist赋初值，对于$S=0$，对于其他点为$dist=∞$。
2. 每次遍历所有的边，并对其进行$relax$操作。
3. 直到没有松弛操作成功，证明已经找到全局最短路，退出循环。

动态演示：图解贝尔曼-福特算法

分析

由于一次松弛操作会使最短路的边数至少$+1$（考虑极端情况为链）
而最短路的边数最多为$n-1$。（即源点与每个点都链接）

所以最多执行$n-1$次松弛操作，即最多循环$n-1$次。

伪代码

for (i = 1 -> N) dist[i]=INF, dist[S]=0;	//初始化dist

for (i = 1 -> N-1)		//最多执行N-1次全局松弛
	for (ALL edge) relax(edge.s, edge.e);	//遍历每条边

relax(u, v)
{
	dist[v] = min(dist[v], dist[u]+edge_len(u, v));
}

时间复杂度

$O(NM)$（不理解可以看上方动态演示）

额外应用

• 判断是否存在负环

  跑Bellman-Ford算法，如果在$n-1$次之内求得最短路算法结束，则不存在负环，反之一定存在。

优化

• 当某次全局松弛时，并没有松弛操作成功（没有松弛），证明已经找到所有最短路，可以break。
• 用队列优化，即SPFA算法。

SPFA 算法

实际上为采用队列的Bellman-Ford算法，但一般要用就用这个。
而且判断负环方式稍有不同。【故单独写出来祭奠一下x……

额外符号定义

• $que[]$——存被松驰过的点的队列
• $in_queue[u]$——u点是否在松弛队列里

分析

很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。
即使用队列，将松弛的点push进来，基于此点松弛完后再pop出去。

形式上与BFS非常相似。
不同点为：

• BFS中一个点出队了后不会再重新进入序列。（因为搜索会把当前最优解搜索出来）
• SPFA一个点可能在出队后再次进入队列。（因为当前relax的可能会被别的relax再找到较短路。也就是说一个点修改过其他点后，过了一段时间可能会由其他点获得更短路劲，于是又可以用来修改其他点，这样反复循环。即是为接近最优解而非直接到达）

伪代码

que.push(S);
in_queue[S] = true;
while (!q.empty())
{
	u = q.pop();
	in_queue[u] = false;
	for (ALL edge(u--->v))	//遍历u的所有边
		if (!in_queue[v])
		{
			relax(u,v);
			q.push(v);
			in_queue[v] = true;
		}
}

时间复杂度

期望：$O(KE)$（$K$为常数，平均值为$2$；$E$为边数）
最坏：$O(NM)$

仅为Bellman-Ford的优化，极端情况退化成Bellman-Ford。

应用——判断负环

1. BFS1：松弛次数大于n-1。
   部分代码
2. BFS2：入队次数大于n-1。
   部分代码

   以上两者代码极其相近(就调整了个顺序),区别在于按入队次数判断虽然慢（cnt增加的慢）,但更稳（可能存在重边导致了多次松弛）。

3. BFS3：起点到一个点的经过边数大于n-1。
   部分代码

   这个方法较好【？……

4. DFS：遇到在栈内的节点。
   部分代码

   DFS版对于随机数据来说具有较为优秀的表现，但是会被构造数据卡成指数级别的复杂度。【来自洛谷@vectorwyx】

有关两大类方法的疑问见：关于DFS版本的SPFA判负环

注意事项

SPFA很可能被针对卡常数，导致TLE……
故如果没有负环存在，请用Dijkstra……

算法对比

Dijkstra和Floyed是不断的试点。Dijkstra试最优点，Floyed试所有点。

Bellman-Ford和SPFA是不断的试边。Bellman-Ford是盲目的试所有边，SPFA只试那些有利用价值的点的边。

总结

如果是非负权图，求单源最短路请用Dijkstra，否则很容易卡常导致TLE…… 除非要判定负环，或报告最短路不存在，才用SPFA……

例题

• P3125 Bessie’s Birthday Buffet S

  考点：图上动规、最短路
  本地代码+题目分析+SPFA讲解+WA记录+参考题解