Floyd算法详解：图的邻接矩阵实现最短路径

"本文主要介绍了如何使用图的邻接矩阵存储结构来实现Floyd算法，以查找图中每对顶点之间的最短路径。" 在图论和算法领域，Floyd算法，也称为Floyd-Wallshall算法，是一种用于寻找图中所有顶点对之间最短路径的有效方法。该算法的核心思想是逐步考虑中间节点，通过动态规划更新每对顶点之间的最短路径。Floyd算法的时间复杂度是O(n^3)，其中n是图中顶点的数量。 在邻接矩阵的存储结构中，图中的每个顶点用一维数组索引表示，而矩阵的每个元素代表对应顶点间边的权重。若顶点i与顶点j之间存在边，矩阵的[i][j]位置就存储这个边的权重；若不存在边或者边的权重为无穷大（表示不可达），则通常设置为一个非常大的数或负无穷。 在给出的代码段中，`MDNet::Floyd(CDC *pDC)`函数展示了Floyd算法的具体实现。首先，定义了一个二维的`path`数组和`D`数组，分别用于存储每对顶点之间的最短路径和最短路径的长度。初始化阶段，`D`数组的对角线元素初始化为0，表示顶点到自身的路径长度为0，其他非对角线元素根据邻接矩阵`arcs`初始化为相应边的权重。`path`数组则记录了每对顶点之间的初始路径，即直接连接它们的边。 接下来，算法通过三重循环遍历所有顶点，依次尝试将当前中间节点k加入到每对顶点u和v的路径中，判断是否能形成更短的路径。如果通过k的路径（D[u][k]+D[k][v]）小于当前已知的最短路径D[u][v]，则更新D[u][v]的值，并更新对应的最短路径记录`p[u][v]`。 在示例中，算法被应用在一个简单的图上，展示了在不同阶段如何检查并更新最短路径。一开始，D(-1)表示初始状态，之后的D(0)表示考虑了节点a后的情况。在这个过程中，算法检查所有可能的路径组合，例如，发现通过节点a并不能使b到c的路径变得更短，因此保持原来的最短路径不变。 通过Floyd算法，我们可以得到图中所有顶点对之间的最短路径，这对于解决诸如网络路由、交通路线规划等问题非常有用。尽管Dijkstra算法可以找到单源最短路径，但若需要计算所有顶点对的最短路径，Floyd算法更为高效。