CodeForces 295B Greg and Graph
题解
\(Floyd\) 算法是一种基于动态规划的算法，以此题为例介绍最短路算法中的 \(Floyd\) 算法。
我们考虑给定一个图，要找出 \(i\) 号点到 \(j\) 号点的最短路径。则该最短路径只有两种可能：
-
\(i\) 号点直接到达 \(j\) 号点的路径中产生最短路径
-
\(i\) 号点经过一些中间点到达 \(j\) 号点的路径中产生最短路径
我们添加一个点 \(k\)，使得 \(i\) 号点到 \(j\) 号点添加后产生的最短路径比添加前的最短路径更短，则称该操作为松弛。
下面我们以从一个示例开始介绍算法的步骤。
示例
给定一个赋权有向图，如下图：
算法步骤
我们声明一个集合 \(S\)，并称该集合为中转集合。
我们声明一个 \(dist\) 数组，其中 \(dist[i][j]\) 表示从源点 \(i\) 号点只经过中转集合中的点，到达目标点 \(j\) 号点的最短路径。
每一轮更新都更新 \(dist\)，直到集合 \(S\) 为图的顶点集 \(V\)。
初始化更新
\(S\) 初始化为：
\[S = \{ \} \]\(dist\) 数组根据我们的定义，此时 \(dist[i][j]\) 表示不经过图中的任何顶点，直接从源点 \(i\) 号点到达 \(j\) 号点的最短距离，为了方便书写，我们此处采用图的邻接矩阵表示。
\[dist[i][j] = graph[i][j] \quad \forall i,j \in V \]故 \(dist\) 被初始化为：
\[dist = \begin{bmatrix} 0 & 5 & 10 & inf & inf \\ inf & 0 & inf & 5 & 15 \\ inf & 30 & 0 & 20 & inf \\ 10 & inf & inf & 0 & 25 \\ 40 & inf & inf & inf & 0 \end{bmatrix} \]第一轮更新
\(S\) 初始化为：
\[S = \{ 0 \} \]\(dist\) 数组根据我们的定义，此时 \(dist[i][j]\) 表示由图中 \(0\) 号点中转，直接从源点 \(i\) 号点到达 \(j\) 号点的最短距离。该最短路径有两种可能：
- 最短路径经过 \(0\) 号点；
- 最短路径不经过 \(0\) 号点；
对于第 \(1\) 种情况说明 \(0\) 号点可以松弛之前的最短距离。这两种情况可以统一表示为下式：
\[\begin{align} dist[i][j] = \min \left( dist[i][j],dist[i][0] + dist[0][j] \right) \quad \forall i,j \in V \tag{1} \end{align} \]此处我们应该注意一下更新的顺序问题，上式表达的含义应该是指只由上一轮的 \(dp[i][j]\)、\(dp[i][0]\) 和 \(dp[0][j]\) 来更新出这一轮的 \(dp[i][j]\)。更准确地说应该可以扩展下数组 \(dist\) 的维度。 如下图所示：
其中 \(k\) 表示这是第 \(k\) 轮更新。按我们的意思，应该写成：
\[dist[i][j][1] = \min \left( dist[i][j][0],dist[i][0][0] + dist[0][j][0] \right) \quad \forall i,j \in V \]即只由第 \(0\) 轮的 \(dp[i][j]\)、\(dp[i][0]\) 和 \(dp[0][j]\) 来更新出第 \(1\) 轮的 \(dp[i][j]\)。那我们为什么可以写成式 \(1\) 的样子？原因在于 \(dp[i][0]\) 和 \(dp[0][j]\) 在此轮更新循环中，始终都没有被更新。
故 \(dist\) 被初始化为：
\[dist = \begin{bmatrix} 0 & 5 & 10 & inf & inf \\ inf & 0 & inf & 5 & 15 \\ inf & 30 & 0 & 20 & inf \\ 10 & 15* & 20* & 0 & 25 \\ 40 & 45* & 50* & inf & 0 \end{bmatrix} \]第二轮更新
\(S\) 初始化为：
\[S = \{ 0, 1 \} \]\(dist\) 数组根据我们的定义，此时 \(dist[i][j]\) 表示从源点 \(i\) 号点出发，只经过中转集合 \(S\) 中的点，到达 \(j\) 号点的最短距离。该最短路径有两种可能：
- 最短路径经过 \(1\) 号点；
- 最短路径不经过 \(1\) 号点；
对于第 \(1\) 种情况说明 \(1\) 号点可以松弛之前的最短距离。这两种情况可以统一表示为下式：
\[dist[i][j] = \min \left( dist[i][j],dist[i][1] + dist[1][j] \right) \quad \forall i,j \in V \]我们接着就要问了，为什么经过 \(1\) 号点的最短路径距离等于 \(dist[i][1] + dist[1][j]\)。在第一轮更新的时候容易想到，但这轮更新（第二轮更新）中，该问题需要仔细思考一下。
经过 \(1\) 号点的路径这样表示：\(i\)(源点) \(\to\) \(1\) \(\to\) \(j\)(目标点)。而经过 \(1\) 号点的最短路径一定是由 \(i\) 到 \(1\) 的最短路径和 \(1\) 到 \(j\) 的最短路径构成（反证法即可得）。
故 \(dist\) 被初始化为：
\[dist = \begin{bmatrix} 0 & 5 & 10 & 10* & inf \\ inf & 0 & inf & 5 & 15 \\ inf & 30 & 0 & 20 & inf \\ 10 & 15* & 20* & 0 & 25 \\ 40 & 45* & 50* & inf & 0 \end{bmatrix} \]