主页
Featured image of post ACM学习笔记——最短路……

ACM学习笔记——最短路……

图论——最短路……

文章字数:1881
预计阅读时长: 分钟

该笔记还未完成整理,待日后继续整理……

该笔记目前直接复制的之前的笔记,还未调整格式。页面格式、内容、链接等可能存在混乱错误……

最短路问题

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

算法

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……

算法对比

Floyd Bellman-Ford Dijkstra Johnson
每对结点之间的最短路 单源最短路 单源最短路 每对结点之间的最短路
没有负环的图 任意图(可以判定负环是否存在) 非负权图 没有负环的图
\(O(N^3)\) \(O(NM)\) \(O(M\log M)\) \(O(NM\log M)\)

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

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

总结

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

例题