图论——最短路学习笔记

其实是复习性质的，主要是总结，证明什么的，等上大学再说。

定义

单源最短路：从一个点 (q) 出发，到其他所有点的最短路。
全源最短路：任意两点见最短路。

算法对比

算法	Floyd	Johnson	Bellman–Ford	SPFA	Dijkstra
类型	全源	全源	单源	单源	单源
作用于	任意图	任意图	任意图	任意图	非负权图
检测负环	能	能	能	能	不能
时间复杂度	(mathcal{O}(n^3))	(mathcal{O}(nm log m))	(mathcal{O}(nm))	(mathcal{O}(m))－(mathcal{O}(nm))	(mathcal{O}(n^2))－(mathcal{O}(m log n))

总结：

没有负环用 dijk，理论上，稠密图（有 (m) 与 (n^2) 同阶）用朴素的，稀疏图（有 (m ll n^2) 的）用堆优化。
有负环优先用 SPFA，即使她被卡也比 BF 快一点。
多源用 Floyd，因为不会 Johnson。

Dijkstra

过程

设两个集合：「已确定最短路长度的集合 (S)」和「未确定最短路长度的集合 (T)」，每次从 (T) 中选取一个最近的，加入集合 (S) 并松弛，更新其他点的最短路。直到 (T) 集合为空。

代码：

int n, m, g[N][N];
array dis, vis;	// 到这个点的最短路，是否已经确定最短路
int gett() {
	int t = -1;
	for (int i = 1; i  dis[i])) t = i;
	return t;
} void dijkstra(int s) {
	dis.fill(0x3f); dis[1] = 0;
	for (int i = 0; i

时间复杂度：(mathcal{O}(n^2))。

堆优化

每成功松弛一条边 ((u,v)) ，就将 (v) 插入堆中，如果 (v) 已经在堆中，直接修改相应元素的权值即可，每次查找操作直接取堆顶结点即可。

代码：

using pii = pair;
array dis, st;	// 到这个点的最短路，是否在堆中
#define v e[i]
void dijkstra(int s) {
	dis.fill(0x3f); dis[s] = 0;
	priority_queue, greater> heap;
	heap.push({0, s}); while (heap.size()) {
		pii t = heap.top(); heap.pop();
		int u = t.second, d = t.first;
		if (st[u]) continue; st[u] = true;
		for (int i = h[u]; i != -1; i = ne[i])
		if (dist[v] > d + w[i]) dis[v] = d + w[i], heap.push({dis[v], v});
	} return (void)("rp++");
}

共计 (mathcal{O}(m)) 次二叉堆上的插入操作，(mathcal{O}(n)) 次删除堆顶操作，而插入和删除的时间复杂度均为 (mathcal{O}(log n))，故时间复杂度：(mathcal{O}((m+n) log n)=mathcal{O}(m log n))。

Bellman–Ford

不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

因为一个图的最短路，在没有负环的情况下，最长只能是 (n-1) 条边，所以松弛 (n-1) 轮即可。

因此可以得出此算法求不超过 (k) 条边的最短路的方法，即松弛 (k) 轮。

int n, m, k;
struct Edge { int a, b, w; } edges[M];
array dis;
void bellman_ford(int s) {
	dis.fill(INF); dis[s] = 0;
	for (int i = 0; i

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 (+1)，而最短路的边数最多为 (n-1)，因此整个算法最多执行 (n-1) 轮松弛操作。故总时间复杂度为 (mathcal O(nm))。

队列优化 Bellman–Ford——SPFA

SPFA 说的通俗点叫 Bellman–Ford 的队列优化（BFS）版。

原理是，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。

代码：

int h[N], w[N], e[N], ne[N], idx;
array dis, st;	// 到这个点的最短路，是否在队列中
#define v e[i]
void spfa(int s) {
	dis.fill(INF); dist[1] = 0;
	queue q; q.push(1);
	st[1] = true;
	while (q.size()) {
		int u = q.front(); q.pop();
		st[u] = false;
		for (int i = h[u] ; i != -1 ; i = ne[i])
		if (dist[v] > dis[u] + w[i]) {
			dist[v] = dis[u] + w[i];
			if (!st[v]) q.push(v), st[v] = true;
		}
	}
}

栈优化 Bellman–Ford——找负环

通常用于判负环，不用像 SPFA 那样判进队次数的原因是：DFS 在栈内的只有祖先，而 BFS 有非祖先。

int dis[N], vis[N]; // 提前将 dis 赋为 INF
bool dfs_spfa(int u) {
	if (vis[u]) return true; vis[u] = true;
	for (int i = h[u]; i != -1; i = ne[i])
	if (dis[e[i]] > dis[u] + w[i]) {
		dis[e[i]] = dis[u] + w[i];
		if (dfs_spfa(e[i])) return true;
	} return vis[u] = false;
}

Floyd

一个很实用的全源最短路解法，特点是好写，容易拓展。

时间复杂度：(mathcal O(n^3))。

代码：

for (k = 1; k

Johnson

不会，现阶段不打算学。

Reference

[1] https://oi-wiki.org/graph/shortest-path/

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net

图论——最短路 学习笔记

定义