5. Floyd算法

Floyd算法 ： 求图中任意一对顶点间的最短路径；

通常用方阵来表示图中每两点之间的最短路径的过程
方阵的阶数越高，计算量越大！
下面通过四阶方阵来演示通过Floyd算法求图中任意两点间的最短路径

算法流程：

1. 初始化
   设置两个矩阵A[ ][ ]和Path[ ][ ]
   其中A用来记录当前已经求得的任意两个顶点最短路径长度；Path用来记录当前两顶点间最短路径上要经过的中间顶点
   初态：

矩阵的下标代表每一步中所选的中间点，初始化时从0顶点开始，没有中间点，故下标设为－1

2. 执行过程：
   依次以0，1，2，... ...为中间点，每次检测所有顶点对
       设此时以t为中间点，当检测的顶点对为{ i , j }
       若A[i][j] > A[i][t] +A[t][j]，则将A[i][j]改为后者的值，并且将Path[i][j]改为t
   得到最终矩阵A和Path，由A可查出图中任意两点间的最短路径长度，由Path可算出任两点间最短路径的顶点序列

示例

Floyd算法代码实现