Floyd多源最短路径算法图解

Floyd算法

Floyd是经典的多源最短路径算法，利用动态规划的思想来寻找多源点之间的最短路径。在具体的体重表中。该算法的时间复杂度为O(n3)。之所以叫Floyd，是因为该算法的创始人之一是1978年图灵奖获得者、斯坦福大学计算机教授学院的罗伯特·Floyd。

核心思想

对于n个点的带权图，从带权图的带权矩阵开始，更新n次，最终得到每两点之间最近路径的矩阵。即带权图的邻接矩阵为，矩阵按照一定的公式递归更新。初始矩阵为D(0)。首次利用D(0)根据公式构造矩阵D(1)；求积时，用D(1)根据公式构造矩阵D(2)；以此类推，用D(n-1)根据公式构造矩阵D(n)。 D(n)是图的距离矩阵，第i行j列表示顶点i到顶点j的最近距离。

动态规划

如何理解这个动态规划算法？可以理解为逐一选择一个中转点，那么对于这个中转点，所有其他以此为中转点的点都必须按照规定进行更新。这个规定是，如果两个原始点之间的距离经过这个转移点变小，就会更新。距离矩阵。例如选择“1”作为中转点，“02”之间原来的距离为5，经过中转点1后（即路径变为“012”），距离变为4，变小。 。然后更新距离矩阵的相应元素。 ，从5更新为4。当图中所有顶点都被处理为转移点时，得到的最终距离矩阵为多源最近距离矩阵。

所以 是 i 和 j 之间的最近距离，其中中间节点的数量不超过 k。当k=0时，，对于有n个顶点的图，要求i到j的最近距离为。

现在我们在和之间建立递归关系。对于任意k，，那么根据这个递归关系就可以得到最后一条最短路径，即到中间节点号最近的路径不超过n-1距离。

算法流程

1. 从一条单边路径开始，两点之间的距离就是边权重。如果没有边连接两点，则权重是无限的。即用数组记录i和j之间最近的距离。最初，如果 i=j，则 dis[i][j]=0。如果两个点 i 和 j 连接，则 dis[i][j] 的值为边权重。如果两点 i 和 j 不相连，则 dis[i][j] 的值为无穷大。
2. 对于每对顶点u和v，查看是否存在一个顶点w使得从u到w到v的路径比已知路径短，如果有则更新。即对于k的所有值(1