经典算法——弗洛伊德算法

大家好，欢迎来到IT知识分享网。

弗洛伊德算法（Floyd-Warshall Algorithm）

一、概念与用途

弗洛伊德算法是一种解决所有对任意顶点间的最短路径问题的动态规划方法。在有向加权图中，它能够计算出从任意一个顶点到其他所有顶点的最短路径及其长度。

二、算法原理

1. 初始化：

创建一个n×n的矩阵 dist，其中 dist[i][j] 表示从顶点i到顶点j的初始距离，对于不存在的边，其值可以设置为无穷大。

2. 动态规划迭代：

对于每一对顶点 (k, i) 和 (k, j)，如果通过顶点k作为中间点能使路径 i -> k -> j 的总距离小于当前已知的最短路径 i -> j 的距离，则更新 dist[i][j] 为新的更短距离。

3. 迭代结束条件：

当所有可能的中间节点都考虑过后，dist 矩阵中的元素即表示从每个顶点到其他所有顶点的最短路径长度。

三、C++ 示例代码片段

#include <iostream> #include <limits> using namespace std; const int MAX = 5; // 假设图有5个顶点 int dist[MAX][MAX]; // 存储最短路径信息的矩阵 void floydWarshall(int n) { for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dist[i][j] = (i == j) ? 0 : numeric_limits<int>::max(); // 初始化为无穷大或0 // 加载起始时的邻接矩阵数据，这里假设已经存在一个函数 loadAdjMatrix(dist) // 弗洛伊德算法核心迭代过程 for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } } // 主函数部分，加载邻接矩阵数据并调用floydWarshall函数 int main() { // 假设 loadAdjMatrix 函数已经将邻接矩阵数据填充进 dist 矩阵 loadAdjMatrix(dist); floydWarshall(MAX); // 输出结果或者进一步处理最短路径信息 return 0; }

上述代码展示了弗洛伊德算法的基本实现框架。在实际应用中，你需要根据具体问题的输入方式来实现 loadAdjMatrix 函数以加载邻接矩阵数据。

最终得到的 dist 矩阵中，dist[i][j] 就是顶点i到顶点j的最短路径长度。若需要存储最短路径本身，还需要额外的空间记录前驱节点信息以便重构路径。