本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-15 11:49:40

Floyd

Floyd有4个用途：

$\texttt{1.最短路}$

$\texttt{2.传递闭包}$

$\texttt{3.找最小环}$

$\texttt{4.恰好经过k条边的最短路（倍增）}$

初始化：

$$ d(i,j)=\left\{ \begin{aligned} i {=}\mathllap{/\,}j,d(i,j) = +\infty \ i==j,d(i,j)=0 \ \end{aligned} \right. $$

计算：

$for$ $k$ $\impliedby$ $1 - n$

$for$ $i$ $\impliedby$ $1 - m$

$for$ $j$ $\impliedby$ $1 - n$

$d_{k,i,j} = \min(d_{k-1,i,k} + d_{k-1,i,j} , d_{k-1,i,j})$;

Floyd是怎么DP的呢？

----------------DP 分析---------------- 动态规划

状态表示：$d_{k,i,j}$

集合：$\color{orange}\texttt{所有从i出发，最终走到j，且中间只经过节点编号不超过k的所有路径。}$ 属性：$\color{orange}\texttt{路径长度的最小值}(\min)$

状态计算：

$d_{k,i,j}$

$\texttt{所有不包含节点k的路径}$

$d_{k-1,i,j}$

$\texttt{不包含k就是只用1\~~~k-1这些点从i走到j}$。

$\texttt{所有包含节点k的路径}$。

$i->k->j$

$\texttt{从i出发经过k走到j。}$

$\texttt{我们可以把i\~~~k分成一段，把k\~~~j分成一段。}$

$\texttt{而从i走到k，不论怎么走，并不影响从k走到j。}$

$\texttt{因此我们要求最短路，而且是完全独立的两部分，那么就相当于求A+B,而由于它们是互相独立的，所以我们就取A的最小值B的最小值，相加就能得到从i->k->j的最短路。}$

----------------尝试去掉一维----------------

我们尝试去掉一维，看一看去掉之后，状态转移方程是否等价，如果等价，就可以去掉，否则就不可以去掉。

原方程：

$d_{k,i,j} = \min(d_{k-1,i,k} + d_{k-1,i,j} , d_{k-1,i,j})$

去掉一维后的方程：

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

首先，$d_{k,i,j}$是一定等于$d_{k-1,i,j}$，所以，在取$\min$的时候，不包含$k$的就可以去掉一维。

而第包含$k$的也只用到了$k-1$，所以也可以去掉一维，这样就可以去掉一维了！