前言

好像少了什么

---

定义

在有权图 $G$ 中，求起点 $s$ 到终点 $t$ 的所有路径中权值之和最小的。（如果没有特殊说明，本篇 blog 默认起点为 $1$，终点为 $n$。）

当然，不会有算法只求出点对点的最短路径，而是会从起点 $s$ 出发，求出到所有点的最短路，这就是单源最短路径。也会有一些算法的特性限制了必须维护任意点之间的最短路径，这就是全源最短路径。

例如下面 ↓ 这张图：

很容易看出，$1$ 到 $4$ 的最短路径为 $1\to2\to3\to4$ 这一条，权值之和为 $5$。下面是一些求出最短路的算法。

1. 暴力

这部分用于引入，不给出正确代码。

1 - 1. 暴力枚举

路径其实就是若干个点的排列，例如 $1\to2\to3\to4$、$1\to3\to2\to4$、$1\to3\to4$ 等等。只要排列出所有可能，总能得到最短路的。时间复杂度：$O(n!)$。这种算法只能用来娱乐，没有什么实际用途。伪代码：

ans = INF
way = [1, 2, 3, ..., n - 1, n]
for i = 1 to jc(n): # 循环 n 的阶乘次
	cnt = 0
	for j = 1 to n - 1:
		cnt += g[way[j]][way[j + 1]]
	ans = min(ans, cnt)
  下一个排列
return ans

1 - 2. DFS 深度优先搜索

DFS 本质上也是暴力枚举。但是可以在其中做一些剪枝、记忆化。时间复杂度接近 $O(n!)$。伪代码：

DFS(u, dis):
	if u == n:
		ans = min(ans, dis)
		return
	# 可进行记忆化优化
	for v = 1 to n:
		if g[u][v] != INF and !vis[v]:
			vis[v] = 1
			dfs(v, dis + g[u][v])
return ans

2. BFS 广度优先搜索

BFS 虽然也是搜索，但它不暴力。在 无权图（或权值相等） 中，BFS 保证 第一次访问即是最短路。时间复杂度：$O(n)$。BFS 只能用于 无权图（或权值相等）。

在下面的代码中，$n$ 表示点数，$s$ 表示起点，$dis_u$ 表示到 $u$ 的最短路，$vis_u$ 表示是否访问过 $u$。vector <int> g[N] 利用邻接链表存图。

queue <int> q;
int n, s, dis[N];
vector <int> g[N];
void bfs(int s)
{
	for (int i = 1; i <= n; ++i)
		dis[i] = INF; // 这一步其实可以省略但不建议 
		// 因为 BFS 不依靠 dis 更新，第一次就是最短路。 
	q.push(s);
	vis[s] = 1;
	dis[s] = 0;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		
		for (auto v : g[u])
		{
			if (!vis[v])
			{
				vis[v] = 1;
				dis[v] = dis[u] + 1; // 或加上相等的权值
				q.push(v);
			}
		}
	}
}

3. 经典最短路算法

正文开始。

依旧是这张图，记住它，下面 ↓ 会用到。

3 - 1. Floyd 全源最短路径

Floyd 本质上是动态规划。它利用一个点 $k$ 来更新 $i\to j$ 的最短路。

过程演示

用 dxd 的话来讲，Floyd 的过程可以想象成点亮灯泡。利用点亮的节点更新其余节点。

• 当没有任何节点被点亮时，如图：

  

  除了到自己和直连边，剩下的都是不可达。

• 当点亮 $1$ 点（可利用 $1$ 进行转移）：

  从 $1\sim n$ 遍历起点 $i$。内层从 $1\sim n$ 遍历终点 $j$（这里起点终点只是动态规划里的子问题，并非全局起点终点）。通过 $k$ 点，判断 $i\to j$ 能否更短。当 $i \to k \to j$ 比 $i \to j$ 更短时，就可以更新 $dis_{i,j}$

  当前没有任何点可以更新。

• 当点亮 $2$ 点（可以利用 $\{1,2\}$ 进行转移，但 $1$ 已经在上一轮计算过，所以只有 $2$）：

  如图：

  

  通过 $1 \to 2 \to 3$，权值为 $2+1=3$，相较于原来的最短路 $dis_{1,3}=4$ 更小，所以可将 $dis_{1,3}$ 更新为 $3$。

  同理，通过 $1 \to 2 \to 4$，可将 $dis_{1,4}$ 更新为 $7$。

• 当 $3$ 被点亮时（可利用 $\{1,2,3\}$ 进行转移，同理 $\{1,2\}$ 已经计算过，只需计算 $3$）：

  可以转移 $1 \to 4$：

  • 原来：$\inf$；
  • $1 \to 2 \to 3 \to 4$：$2+1+2=5$。由于 $1 \to 2 \to 3$ 已经被计算过，所以实际上是 $dis_{1,3}+3\to 4=3+2=5$。
  • 虽然还有一条路 $1 \to 3 \to 4$，但实际上这条路的 $1 \to 3$ 这部分已经被替换为 $1 \to 2 \to 3$，所以这条路是不会被计算的。

由此可以发现一些 Floyd 的性质：

1. 是 全源最短路径。可以正确计算出任意两点的最短路径，且每两点之间的路径都可能关系到整个图的计算。
2. 具有 子结构重叠 的特性。例如要计算 $1 \to 3 \to 4$ ，就要先计算 $1\ to 3$。
3. 具有 最优子结构 的特性。例如 $1 \to 3$ 最短，则可以得到 $1 \to 3 \to 4$ 最短。
4. 具有 无后效性。已经计算的 $1 \to 3$ 不会影响 $1 \to 3 \to 4$ 的计算，只要 $1 \to 3$ 计算出来，则 $1 \to 3 \to 4$ 也能计算出来。且 $1 \to 3 \to 4$ 的计算不会影响 $1 \to 3$ 的计算。

可以发现，后 3 点正是动态规划的特性。因此这里按照分析动态规划的方法分析 Floyd。

定义状态变量

定义 $dis_{i,j}$ 表示从 $i$ 到 $j$ 的最短路径。不可达为 $\inf$，即初始时全是 $\inf$。这样取 $\min$ 的时候不会影响到最短路。

状态转移方程

枚举一个 $k$ 表示新点亮的点。从 $1\sim n$ 遍历起点 $i$。内层从 $1\sim n$ 遍历终点 $j$（这里起点终点只是动态规划里的子问题，并非全局起点终点）。通过 $i \to k \to j$ 来更新 $i \to j$，即：

$$dis_{i,j}=\min(dis_{i,j},dis_{i,k}+dis_{k,j})$$

枚举完 3 层循环，就可以计算出所有 $dis_{i,j}$。

初始化和边界

• 初始化：如上面 ↑ 的演示所示，先初始化为 $\inf$，再把直连边设为 $w$。
• 边界：没有什么，$k,i,j$ 都是 $[1,n]$。注意 $k$ 循环在最外层，破坏动态规划的无后效性。因为计算第 $k$ 层时依赖于第 $k-1$ 层，第 $k-1$ 层没有填完就不能填第 $k$ 层。

答案

$s$ 到 $t$ 的最短路就是 $dis_{s,t}$。同时 Floyd 可以计算出所有点之间的距离。

分析

时间复杂度：$O(n^3)$，适用于 $n \le 300$。当题目要求任意点之间的最短路径时可以用。

代码

for (int k = 1; k <= n; ++k)
{
	// 可以判断 k 与 i 是否相连，避免多余计算 
	for (int i = 1; i <= n; ++i)
	{
		// 同理可以判断 i 与 j 
		for (int j = 1; j <= n; ++j)
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	}
}