证明求最短路径问题具有最优子结构（动态规划）_证明动态规划算法求最短路问题的最优性

算法导论218页说了很多来说明最长路径问题不能用动态规划算法，最短路径可以。在证明最短路径子问题无关时候应该是默认承认了最短路径的最优子结构的。可是证明最优子结构需要用到复制粘贴法，在用复制粘贴法的时候又不免会因为子问题不是无关的从而不能复制粘贴，所以不能证明最优子结构，这样的话，那段用最优子结构证明子问题无关看得我逻辑有点乱。。。

当然也可能是没仔细看，对书上表达的逻辑理解有误，闲话不多说，我还是用自己的逻辑来理解吧，也能够严谨证明。

我断言最短路径问题满足最优子结构，最长路径不满足，下面证明。

1.证明：最短路径问题满足最优子结构。

    设  是从顶点u到顶点v的最短路径, w是路径内部异于u和v的任一点，推断和也分别是从u到w和从w到v的最短路径。

    下面用反证法证明上面的推断成立。

    1) 若存在路径比更短，并且和无关，即他们不含有除了w之外的公共点。则利用复制粘贴法用代替，这样从u到v就存在更短的路径，这与是u到v的最短路径这一假设矛盾，所以从u到w的所有和无关的路径中，最短

    2) 若存在路径比更短，并且和有关，设存在公共点x，这时候不能用复制粘贴将代替因为最短路径不允许存在环。但是可以将分解为和, 分解为和，

                     =  +  

         由于比更短，与是最短路径矛盾。所以从w到v的所有和有关的路径中，最短。

    综合1)和2)可知是子问题u到w的最短路径。对称的可证明也是顶点w到v的最短路径。所以最短路径问题满足最优子结构。

2.说明为什么最长子问题不满足最优子结构。

    类似于最短路径的例子，在证明步骤2)中，可以假设存在路径比更长，并且和有关，即存在公共点x。因为最长路径不能有环，所以不能代替使得更长，也不能像证明最短路径那样分解。所以没法通过反证法得出存在从u到v的更长路径的矛盾结果，所以假设没法推翻，不一定是子问题中最长路径。因此不满足最优子结构