Floyd
Floyd
Floyd有4个用途：
\texttt{1.最短路} \texttt{2.传递闭包} \texttt{3.找最小环} \texttt{4.恰好经过k条边的最短路（倍增）}
初始化：
\begin{aligned} i {=}\mathllap{/\,}j,d(i,j) = +\infty \\ i==j,d(i,j)=0 \\ \end{aligned} \right.
计算：
for$ $i$ $\impliedby$ $1 - m for$ $j$ $\impliedby$ $1 - n
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} > $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})
首先，
而第包含