如果让 New Bing 来教你 Floyd

Endline · 2023-10-06 17:22:16 · 个人记录

这是写作设置

以下是 New Bing 给出的文章

你好，欢迎来到我的博客，今天我们要学习一个经典的图论算法，叫做 Floyd 算法。这个算法可以用来求解任意两个顶点之间的最短路径问题，也就是说，给定一个有向图，我们可以用 Floyd 算法找出从任意一个顶点出发，到达任意另一个顶点的最短距离。这个算法的思想很简单，就是利用动态规划的方法，不断地更新两个顶点之间的最短距离，直到达到最优解。具体的步骤如下：

1. 初始化一个二维数组 d，其中 d[i][j] 表示从顶点 i 到顶点 j 的距离，如果 i 和 j 之间有边，则 d[i][j] 为边的权值，否则为无穷大。
2. 遍历所有的顶点 k，对于每个 k，再遍历所有的顶点 i 和 j，如果 d[i][k] + d[k][j] < d[i][j]，则更新 d[i][j] 为 d[i][k] + d[k][j]，这表示通过 k 作为中间点，可以缩短从 i 到 j 的距离。
3. 重复步骤 2 直到没有任何更新发生，此时 d[i][j] 就是从 i 到 j 的最短距离。

这个算法的时间复杂度是 O(n^3)，空间复杂度是 O(n^2)，其中 n 是顶点的个数。下面我们来看一个例子：

这是一个有向图，有 4 个顶点和 8 条边。我们用一个 4x4 的数组来表示 d：

首先我们遍历 k = A，对于每个 i 和 j，我们检查是否通过 A 可以缩短从 i 到 j 的距离。例如，对于 i = B, j = D，我们发现 d[B][A] + d[A][D] = 8 + 7 = 15 < ∞ = d[B][D]，所以我们更新 d[B][D] = 15。同理，我们还可以更新 d[C][B] = 8, d[D][B] = 10, d[D][C] = 6。更新后的数组如下：

然后我们遍历 k = B，对于每个 i 和 j，我们检查是否通过 B 可以缩短从 i 到 j 的距离。例如，对于 i = A, j = C，我们发现 d[A][B] + d[B][C] = 3 + 2 = 5 < ∞ = d[A][C]，所以我们更新 d[A][C] = 5。同理，我们还可以更新 d[A][D] = 10, d[C][D] = 3, d[D][A] = 6。更新后的数组如下：

接下来我们遍历 k = C，对于每个 i 和 j，我们检查是否通过 C 可以缩短从 i 到 j 的距离。例如，对于 i = B, j = A，我们发现 d[B][C] + d[C][A] = 2 + 5 = 7 < 8 = d[B][A]，所以我们更新 d[B][A] = 7。同理，我们还可以更新 d[B][D] = 5, d[D][B] = 9。更新后的数组如下：

最后我们遍历 k = D，对于每个 i 和 j，我们检查是否通过 D 可以缩短从 i 到 j 的距离。这一次没有任何更新发生，所以我们得到了最终的结果：

这就是 Floyd 算法的过程和结果，我们可以看到，从任意一个顶点到另一个顶点的最短距离都被计算出来了。这个算法很简洁而且容易理解，但是它也有一些缺点，比如它不能处理负权边的情况，也不能输出最短路径的具体方案。如果你想了解更多关于图论算法的知识，欢迎关注我的博客，我会不定期地更新一些有趣的内容。谢谢你的阅读，希望你能喜欢这篇文章，并且学到一些有用的东西。????