min 与 + 运算转换成类似于矩阵乘法的推导过程

　　记录下由 $\min$ 与 $+$ 运算转换成类似于矩阵乘法的推导过程，有错误请在评论区指出 qwq。

　　我们先简单证明一下矩阵乘法的结合律。设有矩阵 $A_{n \times m}$，$B_{m \times p}$，$C_{p \times q}$，要证明 $(AB)C = A(BC)$。等价于证 $\left({(AB)C}\right)_{i,j} = \left({A(BC)}\right)_{i,j}$，其中 ${A}_{i,j}$ 表示矩阵 $A$ 的第 $i$ 行第 $j$ 列的元素。

$$\begin{align*}\left({(AB)C}\right)_{i,j} &= \sum_{u=1}^{p}{(AB)_{i,u}} \times C_{u,j} \\&= \sum_{u=1}^{p} \left( {\sum_{k=1}^{m}{A_{i,k} \times B_{k,u}}} \right) \times C_{u,j} \\&= \sum_{u=1}^{p} \left( {\sum_{k=1}^{m}{A_{i,k} \times B_{k,u} \times C_{u,j}}} \right) \\&= \sum_{k=1}^{m} \left( {\sum_{u=1}^{p}{A_{i,k} \times B_{k,u} \times C_{u,j}}} \right) \\&= \sum_{k=1}^{m}{A_{i,k} \times \left( \sum_{u=1}^{p}{B_{k,u} \times C_{u,j}} \right)} \\&= \sum_{k=1}^{m}{A_{i,k} \times (BC)_{k,j}} \\&= \left({A(BC)}\right)_{i,j}\end{align*}$$

　　因此根据矩阵乘法的结合律，对于 $\overbrace{A \cdots A}^{n}$ 可以写成 $A^n$，并假设 $n = 2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}$，其中 $k = \left\lfloor \log{x} \right\rfloor$，$\forall i \in [0,k], \ b_i \in \{ {0,1} \}$，利用结合律我们就可以通过 $O(\log{n})$ 的复杂度来计算得到

$$A^n = A^{2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}} = A^{2^{b_k}} \times A^{2^{b_{k-1}}} \times \cdots \times A^{2^{b_0}}$$

　　其中上面的证明过程用到的运算包括 $+$ 与 $\times$ 以及对应的交换律、结合律和分配律。对于矩阵乘法

$$(AB)_{i,j} = \sum_{k=1}^{m}{A_{i,k} \times B_{k,j}}$$

　　为了更一般化，我们用运算符 $\oplus$ 和 $\otimes$ 来代替上面的加法与乘法，得到：

$$(AB)_{i,j} = \bigoplus_{k=1}^{m}{A_{i,k} \times B_{k,j}}$$

　　其中 $\oplus$ 和 $\otimes$ 满足交换律：

$$\begin{array}{center}a \oplus b = b \oplus a \\a \otimes b = b \otimes a\end{array}$$

　　结合律：

$$\begin{array}{center}(a \oplus b) \oplus c = a \oplus (b \oplus c) \\(a \otimes b) \otimes c = a \otimes (b \otimes c) \\\end{array}$$

　　$\otimes$ 对 $\oplus$ 的分配律：

$$a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$$

　　很明显矩阵乘法中的加法 $+$ 和 $\times$ 就分别对应于 $\oplus$ 和 $\otimes$。同时发现把 $\min$ 代入 $\oplus$，$+$ 代入 $\otimes$ ，也满足上面定义的一般形式，只需验证这三个性质均成立即可。

　　交换律：

$$\begin{array}{center}\min \{ a,b \} = \min \{ b,a \} \\a + b = b + a\end{array}$$

　　结合律：

$$\begin{array}{center}\min \left\{ \min\{ a,b \}, c \right\} = \min \left\{ a,\min\{ b,c \} \right\} \\(a+b)+c = a+(b+c)\end{array}$$

　　$+$ 对 $\min$ 的分配律：

$$a + \min \{ b,c \} = \min \{ a+b, a+c \}$$

　　因此有

$$(AB)_{i,j} = \min_{1 \leq k \leq m} \left\{ A_{i,k} + B_{k,j} \right\}$$

　　因此对于由 $\min$ 与 $+$ 所构成的运算是具有结合律的，因此对于 $\overbrace{A \cdots A}^{n}$ 同样可以写成 $A^n$，并且有

$$A^n = A^{2^{b_k} + 2^{b_{k- 1}} + \cdots + 2^{b_0}} = A^{2^{b_k}} \times A^{2^{b_{k-1}}} \times \cdots \times A^{2^{b_0}}$$

　　注意这里的 $A \times B$ 是指两个矩阵间的运算，不是一般意义的矩阵乘法。对于 $\min$ 和 $+$ 有

$$(A \times B)_{i,j} = \min_{1\leq k \leq m} \left\{ A_{i,k} + B_{k,j} \right\}$$

　　而一般意义的矩阵乘法是

$$(A \times B)_{i,j} = \sum_{k=1}^{m}{A_{i,j} \times B_{j,k}}$$

　　我们通过Floyd求最短路这道题目对这个性质进行运用。

　　这里我们不用传统 Flody 的 dp 状态定义，而是定义状态 $f(k,i,j)$ 表示从 $i$ 到 $j$ 且经过不超过 $k$ 条边的所有路径所构成的集合中最短的路径长度。

　　对于任意两点 $(v, w)$ 间的距离，答案就是 $f(n-1, v, w)$，这是因为题目保证没有负环，因此任意两点间的最短路径不会超过 $n-1$ 条边。

　　根据从 $i$ 到 $j$ 的路径中所经过的点 $u$ 来把路径分成两段，其中前面一段 $i \to \cdots \to u$ 经过不超过 $k-1$ 条边，后面一段 $u \to \cdots \to j$ 经过不超过 $1$ 条边。这样就得到状态转移方程：

$$f(k,i,j) = \min_{1 \leq u \leq n} \{ f(k-1,i,u) + f(1,u,j) \}$$

　　这种做法的时间复杂度为 $O(n^4)$。这个时候就可以利用上面的性质来进行优化了。

　　我们把 $f(k,i,j)$ 看成是矩阵 $F^{k}_{n \times n}$ 第 $i$ 行第 $j$ 的元素，因此上面的状态转移方程就变成了

$$F^{k}_{i,j} = \min_{1 \leq u \leq n}\left\{ F^{k-1}_{i,u} + F^{1}_{u,j} \right\}$$

　　矩阵间的运算就是 $F^{k} = F^{k-1} \ F^{1}$，通过递推可以发现有 $F^k = \left( F^1 \right)^k$，而我们最终要求的矩阵就是 $F^{n-1} = \left( F^1 \right)^{n-1}$。

　　这里的 $F^k$ 是一个 $n \times n$ 的矩阵，里面的每一个元素 $F^{k}_{i,j}$ 表示从 $i$ 到 $j$ 经过不超过 $k$ 条边的最短路径。

　　这里就可以用快速幂来求 $F^1$ 的 $n-1$ 次方来得到 $F^{n-1}$，要注意是由 $\min$ 与 $+$ 所构成的运算规则。

　　同时根据定义知道矩阵 $F^0$ 中任意一个元素 $F^{0}_{i,j}$ 表示 $i$ 到 $j$ 不经过任何边的最短路径，因此有

$$F^0 = \begin{bmatrix} 0 & \infty & \cdots & \infty \\ \infty & 0 & \cdots & \infty \\ \vdots & \vdots & \ddots & \vdots \\ \infty & \infty & \cdots & 0 \end{bmatrix}$$

　　$F^{n-1} = F^0 \ \left( F^1 \right)^{n-1}$。

　　这样时间复杂度就降到了 $O(n^3 \log{n})$，虽然还是不如传统的 Flody 算法，但这种做法给了我们很多启示，比如魔法和牛站就是利用这种思想实现的。

　　$O(n^3 \log{n})$ 做法的 AC 代码如下：

　　矩阵乘法笔记：https://www.cnblogs.com/wangruidong03/p/15891893.html

本文来自博客园，作者：onlyblues，转载请注明原文链接：https://www.cnblogs.com/onlyblues/p/17272149.html