Floyd 算法
Floyd 算法
August 12, 2024
弗洛伊德算法
该算法与迪杰斯特拉算法不同，迪杰斯特拉是用于解决单源路径最短问题，而弗洛伊德算法是为了解决多源路径最短问题。
基本思想
先说明：在该问题上使用的思路是 动态规划
首先声明问题：我们要求的是从集合 S 中任意一点到其他点的最短路径。
此处就和迪杰斯特拉算法产生了不同，迪杰斯特拉算法是只要求一个点，而弗洛伊德算法是计算所有点。
故我们可以提出一个比较很容易想，但效率并不高的算法：
是否可以简单地对所有点都使用一遍迪杰斯特拉算法呢？
答案是可以的
并且只需要在标准的迪杰斯特拉算法外侧包裹上一层 for 循环遍历所有的元素即可
但这样效率并不好。
如果使用动态规划的方式来实现，思路如下：
从 \(i\) 到 \(j\) 节点可以看作两种情况，1 是二者直接相连，2 是二者中间经过若干个点相连。
所以，我们假设 \(Dis(i,j)\) 为节点 \(u\) 到节点 \(v\) 的最短路径的距离，对于每一个节点 \(k\) ，我们检查 \(Dis(i,k) + Dis(k,j) < Dis(i,j)\) 是否成立，如果成立，证明从 \(i\) 到 \(k\) 再到 \(j\) 的路径比 \(i\) 直接到 \(j\) 的路径短，我们便设置 \(Dis(i,j) = Dis(i,k) + Dis(k,j)\) ，这样一来，当我们遍历完所有节点 \(k\) ， \(Dis(i,j)\) 中记录的便是 \(i\) 到 \(j\) 的最短路径的距离。
伪代码实现
输入：一个图的邻接矩阵 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的边权，如果没有边则为无穷大（∞）
输出：更新后的邻接矩阵 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的最短路径长度
1. 初始化：
对于每一对顶点 (i, j)，如果 i == j，则 dist[i][j] = 0
如果 (i, j) 有边，则 dist[i][j] = 边的权重
如果 (i, j) 没有边且 i != j，则 dist[i][j] = ∞
2. 对于每个中间顶点 k 从 1 到 n：
3. 对于每个顶点 i 从 1 到 n：
4. 对于每个顶点 j 从 1 到 n：
5. 如果 dist[i][j] > dist[i][k] + dist[k][j]：
6. 更新 dist[i][j] = dist[i][k] + dist[k][j]
7. 返回 distC 代码实现
#include <limits.h>
#define V 4 // 图中顶点的数量
#define INF INT_MAX // 无穷大
void floydWarshall(int dist[V][V]) {
// 更新每对顶点之间的最短路径
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j])
dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短路径
}
int main() {
// 初始化图的邻接矩阵
int dist[V][V] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(dist);
return 0;
}最后更新于