Warshall算法思想及改进[关闭]

Warshall-Floyd 算法 https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm本质上基于这样的想法：利用问题与其更简单而不是更小版本之间的关系。 Warshall 和 Floyd 发布了他们的算法，但没有提及动态规划。尽管如此，这些算法确实具有动态编程风格，并且已被视为该技术的应用。

ALGORITHM Warshall(A[1..n, 1..n])
    //ImplementsWarshall’s algorithm for computing the transitive closure
    //Input: The adjacency matrix A of a digraph with n vertices
    //Output: The transitive closure of the digraph
    R(0) ←A
    for k←1 to n do
        for i ←1 to n do
            for j ←1 to n do
                R(k)[i, j ]←R(k−1)[i, j ] or (R(k−1)[i, k] and R(k−1)[k, j])
    return R(n)

我们可以通过重构其最内层循环来加速上述 Warshall 算法对某些输入的实现

我对上述文字的问题如下

1. 作者所说的想法是什么意思是“利用问题与其更简单而不是更小的版本之间的关系”请详细说明。

2. 正如作者在上面的实现中提到的，我们如何提高速度。

1. 的公式意味着最短路径问题（可以看作传递闭包问题的推广）具有最优子结构 https://en.wikipedia.org/wiki/Optimal_substructure财产;然而，对于这个属性不存在正式的描述（在数学定义的意义上）。最优子结构属性对于适合动态规划的问题是必要的。