floyd算法实现思路及实例代码

正如我们所知道的，Floyd算法用于求最短路径。Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis + Dis < Dis是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis = Dis + Dis，这样一来，当我们遍历完所有节点X，Dis中记录的便是A到B的最短路径的距离。那么，如何填充Path的值呢？很简单，当我们发现Dis + Dis < Dis成立时，就要把最短路径改为A->...->X->...->B，而此时，Path的值是已知的，所以，Path = Path。