前言

最短路是图论中的一个比较重要的部分，许多问题都可以抽象为最短路来解决，常见的求最短路径算法有3种，Floyd，Dijkstra 和 SPFA（Bellman-Ford 的队列优化），下面我们逐一介绍。

1. Dijkstra 算法

Dijkstra 算法一般用于求图的单源最短路，本质上是一个贪心的思想。

朴素 Dijkstra 时间复杂度为 \(O(V^2)\) ，堆优化后时间复杂度为 \(O(V\log_2E)\) 。

代码实现如下：

int Dijkstra(int s, int t) {
	memset(dis, 0x3f3f3f3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	struct poi {
		int d, p;
		bool operator<(const poi& x)const { return d > x.d; }
	};
	priority_queue <poi>q;
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty())
	{
		int u = q.top().p; q.pop();
		if (vis[u])continue;
		vis[u] = true;
		for (int i = 0; i < g[u].size(); i++)
		{
			int v = g[u][i].v;
			if (dis[v] > dis[u] + g[u][i].w) {
				dis[v] = dis[u] + g[u][i].w;
				q.push({ dis[v],v });
			}
		}
	}
	return dis[t];
}

但是当图存在负权边时，算法基本原理就会失效，所以 Dijkstra 不能处理带负权边的图。

那怎么办呢？

2. SPFA 算法

SPFA （ Shortest Path Faster Algorithm ）算法是 Bellman-Ford 算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。 SPFA 算法的时间复杂度为 \(O(kE)\) ，其中 \(k\) 是一个较小的常数。

代码实现如下：

int SPFA(int s, int t) {
	memset(dis, 0x3f3f3f3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	queue <int> q;
	vis[s] = true;
	dis[s] = 0;
	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].v;
			if (dis[v] > dis[u] + g[u][i].w) {
				dis[v] = dis[u] + g[u][i].w;
				if (!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	return dis[t];
}

那我们如何用 SPFA 判断是否存在负环呢？只要维护数组 \(cnt_i\) 代表点 \(i\) 的入队次数，若点 \(cnt_i \ge V\) 则存在负环，到点 \(i\) 的最短路不存在。

\(\text{But!}\)

SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 $ O(VE)$ 。

\(\text{TLE}\) 的几率很大。

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法 SPFA 求最短路。

然后呢？

$ 100 \rightarrow 60；$

\(\text{Ag} \rightarrow \text{Cu}；\)

最终，他因此没能与理想的大学达成契约。

现在，随手卡 SPFA 已成习惯，所以，为了 AK IOI ，在无负权边时，请使用稳定的 Dijkstra 算法，而不是 SPFA。

关于 SPFA ，它死了。

3. Floyd 算法

Dijkstra 和 SPFA 都是求单源最短路，如果题目要求求任意两点的最短路，就要多次调用，未免麻烦。下面介绍 Floyd 算法。

Floyd 算法是求多源最短路的算法。Floyd 算法的思想类似 dp，又称插点法。

维护 \(dis_{i,j}\) 表示点 \(i\) 到 点 \(j\) 的最短路径，那么我们做松弛操作，尝试插入点 \(k\)，看看是否能通过点 \(k\) 走“捷径”，即 \(dis_{i,j} = \min(dis_{i,j},dis_{i,k}+dis_{k,j})\)。

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

代码实现如下：

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

注意：

• 中转点 \(k\) 要放最外面。