Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似¹²⁵。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名¹⁵。
形象化地说,Floyd算法就像一个人在一个城市里找到从任意一个地点到任意另一个地点的最短路线。他先把所有可能的路线都列出来,然后每次选择一个中转站,看看是否可以通过这个中转站使得两个地点之间的距离更短。
如果可以,就更新这两个地点之间的距离,并记录下经过的中转站。这样不断重复,直到遍历完所有的中转站为止。
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9; //定义无穷大
const int MAXN = 100; //定义最大节点数
int n, m; //节点数和边数
int dist[MAXN][MAXN]; //存储每对节点之间的最短距离
int path[MAXN][MAXN]; //存储每对节点之间最短路径上的中转站
void floyd() { //无需传入参数
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]; //更新两点之间的距离
path[i][j] = k; //记录下中转站
}
}
}
}
}
void print_path(int i, int j) { //打印从i到j的最短路径上经过的节点
int k = path[i][j]; //获取中转站
if (k == -1) return; //如果没有中转站,直接返回
print_path(i, k); //递归打印从i到k的路径
cout << k << " "; //打印当前中转站
print_path(k, j); //递归打印从k到j的路径
}
Source: (1) Floyd算法详解——包括解题步骤与编程_SweeNeil的博客-CSDN博客. https://blog.csdn.net/SweeNeil/article/details/88713677
(2) Floyd算法详解 通俗易懂 - 知乎. https://zhuanlan.zhihu.com/p/339542626
(3) Floyd算法_百度百科. https://baike.baidu.com/item/Floyd%E7%AE%97%E6%B3%95
(4) 图最短路径算法之弗洛伊德算法(Floyd) | Echo Blog. https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-floyd
(5) 最短路径问题—Floyd算法详解_Ouyang_Lianjun的博客-CSDN博客. https://blog.csdn.net/qq_35644234/article/details/60875818