Note - 最短路

0x00 前言

好久没写博客了，由于本人太蒟，不会写TJ，只好写了这个。

0x01 性质

• 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。
• 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。
• 对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 \(n\) ，边数不会超过 \(n - 1\) 。

0x02 算法

No.1 Floyd算法

设问

给定一张带权图 \(G\)，求任意两点 \(i\)，\(j\) 之间的最短路。

实现

我们考虑用邻接矩阵存图，定义数组 e[i][j]，表示点 \(i\) 到点 \(j\) 的最短路径。
考虑初始化，显然，当 \(i = j\) 时 e[i][j]的值为 \(0\)，其他情况e[i][j]为 \(i\) 直接到 \(j\) 的边权，如两点没有直接连接，则为 \(+∞\)。

然后，三层循环枚举两点 \(i\) 和 \(j\) 还有 \(k\)，\(i\), \(j\) 为所求，\(k\) 则为从 \(i\) 到 \(k\) 再从 \(k\) 到 \(j\) 中间的转移点。写成代码就是
e[i][j] = min(e[i][j], e[i][k] + e[k][j])
此操作称为松弛

核心代码

for (int k = 1; k <= n; k++) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
		}
	}
}

优缺点

此算法时间复杂度为 \(\mathcal O(n^3)\)，显然对于一些节点数过多的图，是不够高效的。且它不作用于没有负环的图，但它可以处理多源最短路。

No.2 Dijkstra算法

设问

给定一张带权图 \(G\)，以及其中一个节点 \(s\)， 求 \(s\) 到其他任意节点的最短路。

实现

主要思想是，将结点分成两个集合：已确定最短路长度的，未确定的。
最短长度用 dis 数组保存。
一开始dis[i]初始化为 \(s\) 和 \(i\) 这条边的权值，若没有边，则为 \(+∞\)。
并将初始点 \(s\) 加入集合。
然后重复这些操作：

1. 选取一个最短路长度最小的结点，移到集合中。
2. 以这个点为转载点，进行松弛操作。

直到所有点都放在集合中，算法结束。

核心代码1

我是用邻接表存的图

for (int i = 1; i <= n - 1; i++) {
	int u, Min = INT_MAX;
	for (int j = 1; j <= n; j++) {
		if (!vis[j] && dis[j] < Min) {
			Min = dis[j];
			u = j;
		}
	}
	vis[u] = true;
	for (int i = 0; i < g[u].size(); i++) {
		dis[g[u][i].first] = min(dis[g[u][i].first], dis[u] + g[u][i].second);
	}
}

优化

刚才所示的代码时间复杂度为 \(\mathcal O(n^2 + m)\)，还不是很高效。
我们注意到每次求最短路长度最小的结点时，用了一层循环枚举。其实，这是没有必要的，我们可以用一个优先队列求取每次的最小值，这样复杂度就优化为 \(\mathcal O(m \log m)\)

核心代码2

void Dijkstra() {
    dis[s] = 0;
    priority_queue, vector >, greater > > q;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < g[u].size(); i++) {
            if (dis[g[u][i].second] > dis[u] + g[u][i].first) {
                dis[g[u][i].second] = dis[u] + g[u][i].first;
                q.push(make_pair(dis[g[u][i].second], g[u][i].second));
            }
        }
    }
}

优缺点

不能处理负权图

No.3 SPFA算法

简介

SPFA算法其实是Bellman-Ford 算法的一种优化。

实现

我们先来介绍一些Bellman-Ford 算法。
Bellman-Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。
时间复杂度为 \(\mathcal O(nm)\)。

Bellman-Ford 算法对负环的判断

如果从 \(s\) 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 \(n - 1\) 轮，因此如果第 \(n\) 轮循环时仍然存在能松弛的边，说明从 \(s\) 点出发，能够抵达一个负环。

很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。
SPFA 也可以用于判断 \(s\) 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 \(n\) 条边时，说明 \(s\) 点可以抵达一个负环。

核心代码

void SPFA(int s) {
	memset(dis, INF, sizeof(dis));
	dis[s] = 0;
	queue q;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = false;//出队首元素，并将元素标记为出队
		for (int i = 0; i < g[u].size(); i++) {//遍历所以 
			int v = g[u][i].to, z = g[u][i].val;
			if (dis[v] > dis[u] + z) {
				dis[v] = dis[u] + z;
				if (!vis[v]) {//若之前已经入队，则不需要重复入队 
					vis[v] = true;
					q.push(v); 
				}
			} 
		} 
	} 
}

0x03 后记

1.各种最短路算法作用与复杂度表

2.参考资料

OI-WIKI