弗洛伊德算法——动态规划思想的实践
最短路径问题
弗洛伊德算法解决的问题是求图中所有顶点间最短路径。
首先该问题具有最优子结构性质，这意味着当路径的全部子路径最优时，整条路径的长度最优。
则该问题可用动态规划求解。假设得到A->B的最短路径L，若A->D需要途经B，根据最优子结构性质，L一定是A->D最短路径的一段。因此我们可以从简单的情况开始，计算出一部分最短路径，得到的结果用于其他复杂路径的计算。
在图中，最简单两种路径是A直接到B：A->B，以及途经一个节点C到B：A->C->B，我们需要区分这两条路径哪个最短，以求得简单情况下的最短路径。
扩展到复杂路径，A->C、C->B的路径都可能包括其他结点，但其最短路径在计算简单路径时已经得到，所以可以忽略路径内部而看做整体，这也意味着复杂路径本质上与简单路径相同，所以我们也把两者相加与与A->B比较。
虽然问题的复杂程度不同但利用之前计算好的结果能够化繁为简，这是动态规划思想在具体问题中的体现。实现思路
我们分析出，需要完成的步骤是比较A->B和A->C->B的大小以找到AB的最短路径，这个步骤对简单情况和复杂情况都是一致的。所以想法是将图中结点两两组合，并与途径其他结点的路径进行长度比较，得到其中路径较短的分支，就可以记录其长度和途径的结点，以便以后使用。
复杂度分析
需要在两个结点间尝试加入所有其他结点，一共n个结点；
使用邻接矩阵表示，n个结点的两两组合要访问$n^2$次；
而使用邻接表，去除了与自身的组合和不存在的边，所以共访问n*e次。
最终复杂度$O(n^3)$要求
不存在路径长度为负的回路。
