Floyd-Warshall算法

判断有向图是不是有环 #todo

假设有向图中节点编号为0到n-1

问题：所有节点之间的最短路径 子问题$R_{ij}^k$：从节点 $i$ 到节点 $j$ 中间节点编号 $\le k$ 的所有路径。

递推公式：

$$R_{ij}^k=R_{ik}^{k-1}(R_{kk}^{k-1}{)}^{\ast }{R}_{kj}^{k-1}|R_{ij}^{k-1}$$

也就是

1. i到j所有节点都$\le k-1$
2. i到k所有节点都$\le k-1$ 再加上 k到j 所有节点都$\le k-1$
   1. 在DFA转换成正则表达式中，还要考虑一下可能有多个k节点的情况
   2. 这里使用Kleene闭包