编写一个程序exp8-8.cpp,实现求带权无向图中多源最短路径的弗洛伊德算法。
时间: 2024-03-03 16:49:39 浏览: 30
好的,以下是exp8-8.cpp的代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
const int INF = 0x3f3f3f3f;
int n, m;
int d[MAXN][MAXN];
void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
cin >> n >> m;
memset(d, INF, sizeof(d));
for (int i = 1; i <= n; i++) d[i][i] = 0;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
d[u][v] = d[v][u] = w;
}
floyd();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << d[i][j] << " ";
cout << endl;
}
return 0;
}
```
在这个程序中,我们首先定义了最大节点数`MAXN`和无穷大`INF`,然后定义了全局变量`n`和`m`表示节点数和边数。`d`数组用来保存两个节点之间的最短路径长度。
在`main`函数中,我们首先读入节点数和边数,并初始化`d`数组为无穷大。然后我们读入每条边的起点、终点和权值,并将它们存储在`d`数组中。最后我们调用`floyd`函数来计算出每对节点之间的最短路径,并输出结果。
`floyd`函数的实现很简单,就是三重循环,每次更新`d[i][j]`为`d[i][k]+d[k][j]`和`d[i][j]`的较小值。