前言
上文介绍了迪杰斯特拉(Dijkstra)算法，计算网图的某个源点到其余各个顶点的最短路径问题（边权值为非负值），本文介绍另一个求最短路径的算法——弗洛伊德算法，它是计算所有顶点到所有顶点的最短路径，其时间复杂度为 O ( n 3 ) O(n^3) O(n3)，其算法相比Dijkstra算法更加简洁易懂。
算法思路
在迪杰斯特拉算法中，定义了两个一维数组int D[MAXVEX]和 int P[MAXVEX]，D表示源点到其他顶点的最短路径和，P表示对应顶点的最小路径的前驱矩阵。
因为弗洛伊德算法中，以所有顶点为源点，因此应该定义为二维数组int D[MAXVEX][MAXVEX]和 int P[MAXVEX][MAXVEX]，核心思路和迪杰斯特拉算法类似，从源点v到终点w，判断经过中转点k的路径是否比原来的路径更短。
例如下图中，A顶点到B顶点在邻接矩阵中是10，如果经过C顶点中转，则路径和为 4 + 3 = 7 4+3 = 7 4+3=7，显然要比直接路径要短。
D [ v ] [ w ] = m i n { D [ v ] [ w ] , D [ v ] [ k ] + D [ k ] [ w ] } D[v][w] = min\{ D[v][w],\quad D[v][k] + D[k][w] \} D[v][w]=min{ D[v][w],D[v][k]+D[k][w]}
以某一顶点为中转点，遍历所有顶点为源点和终点，如果经过中转点更短，则将D中的相应位置更新。文章来源：https://www.toymoban.com/news/detail-521128.html
以下面这个网图为例，观察一下具体是怎么计算的。文章来源地址https://www.toymoban.com/news/detail-521128.html
到了这里，关于【数据结构】图—弗洛伊德（Floyd）算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
