Floyd算法 换一个更清晰的例子
时间: 2023-11-15 12:10:07 浏览: 36
好的,我们来看一个更具体的例子来理解 Floyd 算法。
假设我们有一个带权有向图,其邻接矩阵如下:
```
0 2 6 4
∞ 0 3 ∞
7 ∞ 0 1
5 ∞ 12 0
```
其中,∞ 表示两个节点之间没有边相连,即权重为无穷大。
我们想要求出任意两点之间的最短路径长度,使用 Floyd 算法可以实现。
首先,我们定义一个二维数组 `dp`,表示从节点 i 到节点 j 的最短路径长度。初始状态下,`dp[i][j]` 的值为图中节点 i 到节点 j 的边权值,如果 i 和 j 之间没有边相连,则其值为无穷大。
然后,我们对 `dp` 数组进行更新,通过中间节点 k 来缩小路径长度。具体操作如下:
遍历所有节点 k,然后再遍历所有节点 i 和 j。如果从节点 i 到节点 j 经过节点 k 可以缩短路径长度,则更新 `dp[i][j]` 的值为 `dp[i][k] + dp[k][j]`。
最终,当遍历完所有节点 k 后,`dp` 数组中存储的就是任意两点之间的最短路径长度。
对于上面的邻接矩阵,经过一次 Floyd 算法的迭代,`dp` 数组会变成如下状态:
```
0 2 5 4
∞ 0 3 ∞
7 9 0 1
5 7 10 0
```
其中,`dp[i][j]` 表示从节点 i 到节点 j 的最短路径长度。可以看到,经过一次迭代后,我们可以找到所有不经过中间节点的最短路径长度。
接下来,我们再进行一次迭代,就可以找到所有经过一个中间节点的最短路径长度。最终,经过三次迭代后,`dp` 数组会变成如下状态:
```
0 2 5 4
7 0 3 8
6 8 0 1
5 7 10 0
```
可以看到,经过三次迭代后,我们已经找到了所有节点之间的最短路径长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)