最短路径-Floyd_warshall算法
Floyd算法，也称为Floyd-Warshall算法，是一种用于解决多源最短路径问题的算法。它可以用于计算任意两点之间的最短路径，并可以用于解决其他相关问题，例如最短路径树和最长路径。
Floyd算法的工作原理是通过动态规划来计算所有点对之间的最短路径。它首先初始化一个距离矩阵，其中每个元素表示两个点之间的初始距离。然后，算法迭代地更新距离矩阵，每次更新都会考虑通过中间节点的路径。
Floyd算法的具体步骤如下：
- 初始化距离矩阵 D，其中 D[i, j] 表示从点 i 到点 j 的初始距离。如果 i 和 j 之间存在直接连接，则 D[i, j] 等于直接连接的距离；否则，D[i, j] 等于无穷大。
- 对于所有中间节点 k，执行以下步骤：
- 对于所有点 i 和 j，更新 D[i, j]：
- 如果 D[i, j] > D[i, k] + D[k, j]，则将 D[i, j] 更新为 D[i, k] + D[k, j]。
- 对于所有点 i 和 j，更新 D[i, j]：
- 算法结束后，距离矩阵 D 中的每个元素将表示两个点之间的最短路径。
状态转移方程为:
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])其中dp[a][b]的意思可以理解为点a到点b的最短路径,所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思为k到j的最短路径.
咱们图解一个案例，初始情况每个点只知道和自己直接相连的点的距离，而其他间接相连的点还不知道距离，比如A-B=2,A-C=3但是B-C在不经过计算的情况是不知道长度的。
加入第一个节点A进行更新计算,大家可以发现，由于A的加入，使得本来不连通的B，C点对和B，D点对变得联通，并且加入A后距离为当前最小,同时你可以发现加入A其中也使得C-D多一条联通路径（6+3），但是C-D联通的话距离为9远远大于本来的(C,D)联通路径2，所以这条不进行更新。
咱们继续加入第二个节点B，这个点执行和前面A相同操作进行。对一些点进行更新。因为和B相连的点比较多，可以产生很多新的路径，这里给大家列举一下并做一个说明,这里新路径我统一用1表示，原来长度用0表示。
AF1=AB+BF=6+2=8 < AF0(∞) 进行更新
AE1=AB+BE=2+4=6 < AE0(∞) 进行更新
CE1=CB+BE=5+5=9 < CE0(∞) 进行更新
CF1=CB+BF=5+6=11<CF0(∞) 进行更新
EF1=EB+BF=4+6=10<EF0(∞) 进行更新
当然，也有一些新的路径大于已有路径不进行更新，例如：
AC1=AB+BC=2+5=7>AC0(3) 不更新
AD1=AB+BD=2+8=10>AD0(6) 不更新……
更多路径这里就不一一列举了。
后序加入C、D、E、F都是进行相同的操作,最终全部加完没有路径可以更新就结束停止。实际上这个时候图中的连线就比较多了。这些连线都是代表当前的最短路径。 这也和我们的需求贴合，我们最终要的是所有节点的最短路径。每个节点最终都应该有5条指向不同节点的边！ 矩阵对应边值就是点点之间最短路径。
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | /**************************************************************** * Description: 给定图G，求任意两点的最短路径，Floyd_warshall算法 * Author: Alex Li * Date: 2024-02-23 12:27:10 * LastEditTime: 2024-08-12 21:26:55 ****************************************************************/ #include <iostream> #include <vector> using namespace std; int main() { // 输入图的节点数 int n; cin >> n; // 初始化距离矩阵 dp，大小为 n x n，存储两点之间的最短路径 vector<vector<int> > dp(n, vector<int>(n)); // 初始化距离矩阵 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { dp[i][j] = 0; // 节点到自身的距离为 0 } else { dp[i][j] = INT_MAX; // 初始化为无穷大（表示两点之间没有路径） } } } // 输入图的边 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int u, v, w; cin >> u >> v >> w; // 输入起点 u，终点 v 和权重 w dp[u][v] = w; // 更新距离矩阵中的对应值 } } // Floyd-Warshall 算法的核心部分 // 三重循环更新距离矩阵，考虑经过节点 k 的所有可能路径 for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 选择直接路径和经过 k 节点的路径中的较小者 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); } } } // 输出最终的最短路径距离矩阵 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << dp[i][j] << " "; // 输出从节点 i 到节点 j 的最短路径距离 } cout << endl; // 输出完一行后换行 } return 0; // 返回 0 表示程序执行成功 } |