Floyd （弗洛伊德）算法简述

   一、Floyd （弗洛伊德）算法简介

   Floyd在1962年由Robert Floyd以其当前公认的形式出版。算法作为三个嵌套for循环的现代公式首先由Peter Ingerman在1962年描述。Floyd 算法是解决图论问题的比较经典的算法，是解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图的最短路径问题。

   Floyd算法是一种动态规划算法，节点间的连接权值可正可负。此算法简单有效，在稠密地图中效果最佳。由于三重循环结构紧凑，在稠密图中效率要高于Dijkstra算法。

   Floyd 算法优点主要体现在 ① 算法简单，容易理解，且代码编写简单。②可以算出任意两个节点之间的最短距离，这是很多路径规划算法所不具有的优势。

   Floyd 算法缺点主要体现在∶时间复杂度比较高，对于稀疏图将会生成稀疏矩阵，极大浪费了储存空间。

---

   二、Floyd （弗洛伊德）算法流程

   1、初始化矩阵，将所有相邻的节点对应的权值写入矩阵，不相邻的节点对应的权值初始化为inf，如下面的例子所示：

   2，初始化结束后，开始进行三重循环，每层循环从第一个节点开始遍历，直至遍历到第n个节点，设最外层循环当前节点为i，中间层循环的当前节点为j，内层循环的当前节点为k，且i≠j≠k。则以节点i为中介点，以节点j为起点，节点k为目标点，判断由起点j经由中介点i到达目标点k的代价值是否小于由起点j直接到目标点k的代价值，若小于，则将从起点j到目标点k的代价值d[j][k]更新为d[j][i]+d[i][k]。三重循环结束后，路径规划结束。

   接着以上面的例子继续举例

   ① 以A为中介点，分别更新B/C/D/E/F/G经中介点A到其他节点的累积权值

   ② 以B为中介点，分别更新A/C/D/E/F/G经中介点B到其他节点的累积权值

   ③ 以C为中介点，分别更新A/B/D/E/F/G经中介点C到其他节点的累积权值

   ④ 以D为中介点，分别更新A/B/C/E/F/G经中介点D到其他节点的累积权值

   ⑤ 以E为中介点，分别更新A/B/C/D/F/G经中介点E到其他节点的累积权值

   ⑥ 以F为中介点，分别更新A/B/C/D/E/G经中介点A到其他节点的累积权值

   ⑦ 以G为中介点，分别更新A/B/C/D/E/F经中介点G到其他节点的累积权值

---

   3、路径规划结束后，图的邻接矩阵D也就更新完成了，如果从Vi到Vj有路可达，则D[i][j]=d，d表示该路的长度；否则D[i][j]=无穷大。定义一个矩阵P用来记录所插入点的信息，P[i][j]表示从Vi到Vj需要经过的点，初始化P[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，D[i][j] = min( D[i][j], D[i][k]+D[k][j] )，如果D[i][j]的值变小，则P[i][j]=k。在D中包含有两点之间最短道路的信息，而在P中则包含了最短通路径的信息。

   比如，要寻找从V5到V1的路径。根据P，假如P(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果P(5,3)=3，说明V5与V3直接相连，如果P(3,1)=1，说明V3与V1直接相连。

   进一步来说，假设从1到4的最短路径为1→2→3→4，则以P（1，4）开始在P中查询，P（1,4）里面记录的是当前点（也就是1点）的下一个路径点，即P（1,4）=2，则进一步查询P（2,4）的值，即为3，则进一步查询P（3,4），即为4，也就是我们需要的终点，终止查询，找到最短路径1→2→3→4。

---