c++定义了18个节点的图怎么输出每个节点间的距离
时间: 2024-05-15 07:12:54 浏览: 12
你可以使用 Floyd 算法来计算每个节点间的最短距离。具体步骤如下:
1. 定义一个 18x18 的二维数组 dist,表示每个节点间的距离。
2. 初始化 dist 数组,如果节点 i 和节点 j 之间有边相连,则 dist[i][j] = w(i, j),否则 dist[i][j] = INF(INF 表示无穷大)。
3. 使用三重循环遍历所有节点,计算 dist[i][j] 和 dist[i][k] + dist[k][j] 的较小值,更新 dist[i][j]。
4. 循环结束后,dist 数组中存储的就是每个节点间的最短距离。
下面是一个简单的实现代码,假设节点编号从 0 到 17:
```c++
const int INF = 0x3f3f3f3f;
int dist[18][18];
void floyd() {
// 初始化 dist 数组
for (int i = 0; i < 18; i++) {
for (int j = 0; j < 18; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = INF;
}
}
}
// TODO: 根据图的实际情况初始化 dist 数组
// Floyd 算法求最短路
for (int k = 0; k < 18; k++) {
for (int i = 0; i < 18; i++) {
for (int j = 0; j < 18; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main() {
// TODO: 定义图并初始化
floyd();
// 输出每个节点间的距离
for (int i = 0; i < 18; i++) {
for (int j = 0; j < 18; j++) {
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)