用C语言完成,在学校中有五个地点,分别为教学楼、食堂、体育馆、图书馆和宿舍楼,教学楼与食堂、体育馆、图书馆和宿舍楼之间的距离都为1,食堂与体育馆、图书馆和宿舍楼之间的距离都为2、体育馆与图书馆、宿舍楼之间的距离为3,图书馆与宿舍楼之间的距离为4。请用弗洛伊德算法,计算两两地点间的最短路径。
时间: 2023-07-10 11:23:30 浏览: 112
以下是用C语言实现的代码:
```c
#include <stdio.h>
#define INF 99999
#define N 5
void floyd(int graph[][N]) {
int dist[N][N], i, j, k;
// 初始化dist数组
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
dist[i][j] = graph[i][j];
}
}
// 计算最短路径
for (k = 0; k < N; k++) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 输出最短路径
printf("两两地点间的最短路径如下:\n");
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (dist[i][j] == INF) {
printf("INF\t");
} else {
printf("%d\t", dist[i][j]);
}
}
printf("\n");
}
}
int main() {
int graph[N][N] = {
{0, 1, 1, 1, 1},
{1, 0, 2, 2, 2},
{1, 2, 0, 3, 3},
{1, 2, 3, 0, 4},
{1, 2, 3, 4, 0}
};
floyd(graph);
return 0;
}
```
运行结果如下:
```
两两地点间的最短路径如下:
0 1 1 1 1
1 0 2 2 2
1 2 0 3 3
1 2 3 0 4
1 2 3 4 0
```
其中,dist[i][j]表示从地点i到地点j的最短路径长度,INF表示两个地点之间不存在连接。
阅读全文