给定一个n个顶点的带权连通图G,边上的权值用邻接矩阵a来表示,a[][i]表示边<ij>上的权值,现在使用动态规划思想的Floyd算法,求出任意两个顶点间的最短路径。
时间: 2024-02-12 11:05:00 浏览: 110
使用动态规划思想的 Floyd 算法可以求解任意两个顶点之间的最短路径。其时间复杂度为 $O(n^3)$,适用于稠密图。
算法步骤:
1. 初始化:令 $D^{(0)}=a$,其中 $a$ 为邻接矩阵,$D^{(0)}_{ij}$ 表示顶点 $i$ 到顶点 $j$ 的最短路径长度,$D^{(0)}_{ij}=a_{ij}$,若 $i \neq j$ 且 $a_{ij}=0$,则 $D^{(0)}_{ij}=\infty$。
2. 递推求解:对于 $k=1,2,\cdots,n$,依次计算 $D^{(k)}$,其中 $D^{(k)}_{ij}$ 表示顶点 $i$ 到顶点 $j$ 经过顶点 $1, 2, \cdots, k$ 中的某些顶点的最短路径长度。
$$
D^{(k)}_{ij} = \min\{ D^{(k-1)}_{ij}, D^{(k-1)}_{ik} + D^{(k-1)}_{kj}\}
$$
3. 输出结果:$D^{(n)}$ 即为所求的任意两个顶点之间的最短路径长度。
下面是使用动态规划思想的 Floyd 算法的 C++ 代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
int n;
cin >> n;
int a[n][n], d[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> a[i][j];
if(a[i][j] == 0 && i != j) // 若边权为0,则初始化为无穷大
d[i][j] = INF;
else
d[i][j] = a[i][j];
}
}
// Floyd算法
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
// 输出任意两个顶点之间的最短路径长度
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << d[i][j] << ' ';
}
cout << endl;
}
return 0;
}
```
阅读全文
相关推荐
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044937.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.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)