最短路径之Floyd算法（一种巧妙的证明思路）.md

谈起floyd算法,一般我们会说这是一个动态规划算法.(怪不得如此优美)

为什么是个动态规划算法?因为它有递推公式:d[i][j]=min(d[i][j],d[i][k]+d[k][j])

还有一点就是三重循环,k要写外面,里面的i,j是对称的,随便嵌套没所谓.

这大概就是我们大部分人对floyd算法的了解.

那么,我们其实没有解决核心问题,为什么这样就能解决问题,为什么是这个递推公式,是这个嵌套顺序?

公式：

for (int k = 0; k < N; K++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);}

其中一种证明思路如下:

算法导论上的一个引理4.21：

最短路径的子路径也是最短路径

即如果i点到j点的最短路径上有一点k,那么dp[i][k] + dp[k][j] == dp[i][j]

可以根据这个定理来证明

假设x是i和j之间最短路径经过的点中，索引值最大的一个点

虽然不能保证每一次dp[i][k]和dp[k][j]都是最小的，

但是能保证k 取到 x的时候，得到的结果dp[i][j]是我们想要的最短路径。

可以用数学归纳法证明 假设x1,x2是i, j最短路径中，i k 段的最大索引和k j 段的最大索引，很明显x1 < x, x2 < x; 根据结论，

k == x1时，dp[i][k]为最小值

k == x2时，dp[k][j]为最小值

所以当k == x时，dp[i][j] = dp[i][k] + dp[k][j]成立