用 Floyd 算法求任意两点间的最短路径及最短路长

资 源 简 介

用 Floyd 算法求任意两点间的最短路径及最短路长

详 情 说 明

Floyd算法是一种经典的动态规划算法，用于求解带权图中任意两点之间的最短路径问题。该算法以邻接矩阵作为输入，通过逐步更新矩阵中的值来得到最终的最短路径结果。

算法核心思想是利用中间节点来优化路径距离。对于图中的每一个顶点k，我们考虑将其作为中间节点，检查通过k是否可以缩短顶点i到顶点j的路径距离。如果发现更短的路径，就更新对应的距离值。

算法的实现过程可以分为三个主要步骤：初始化阶段、迭代更新阶段和路径重建阶段。初始化阶段使用给定的邻接矩阵D0，其中对角线元素设为0，表示节点到自身的距离为0；不可达的节点间距离设为无穷大。

迭代更新阶段是Floyd算法的核心部分。通过三重循环来更新距离矩阵：外层循环遍历所有可能的中间节点k，中间和内层循环分别遍历所有的起点i和终点j。在每次迭代中，算法会比较直接从i到j的距离和通过k中转的距离，取较小者作为新的距离值。

路径重建阶段可以在距离矩阵计算完成后进行。通过维护一个路径矩阵，记录下最短路径所经过的中间节点，就可以回溯出具体的路径。

Floyd算法的时间复杂度为O(n³)，其中n是图中节点的数量。这使得它特别适合用于稠密图的最短路径计算。尽管时间复杂度较高，但算法的实现非常简洁，且能够一次性计算出所有点对之间的最短路径。

值得注意的是，Floyd算法可以处理带有负权边的图，但不能处理包含负权回路的图，因为这种情况下最短路径可能不存在（可以无限绕行负权回路来减小路径长度）。