用c语言实现以下功能:用佛洛伊德算法求出已知无向图任意两点间的最短路径,并输出该最短路径及其长度
时间: 2024-01-21 11:16:18 浏览: 86
以下是用C语言实现佛洛伊德算法求出任意两点间最短路径的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define INF 99999 // 定义正无穷
int main()
{
int n, m; // n表示顶点数,m表示边数
scanf("%d %d", &n, &m);
int dist[n][n]; // 定义距离矩阵
// 初始化距离矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = INF;
}
}
}
// 读入边的信息,更新距离矩阵
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
dist[u][v] = w;
dist[v][u] = w; // 无向图需要更新两个方向
}
// 佛洛伊德算法
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 输出每对顶点间的最短路径和路径长度
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
printf("从%d到%d的最短路径是:", i, j);
int k = j;
printf("%d", k);
while (k != i) {
for (int t = 0; t < n; t++) {
if (dist[i][t] + dist[t][k] == dist[i][k]) {
k = t;
printf("<-%d", k);
break;
}
}
}
printf("\n路径长度为:%d\n", dist[i][j]);
}
}
return 0;
}
```
示例输入:
```
6 10
0 1 1
0 2 12
1 2 9
1 3 3
2 4 5
3 2 4
3 4 13
3 5 15
4 5 4
5 0 7
```
示例输出:
```
从0到1的最短路径是:1
路径长度为:1
从0到2的最短路径是:1<-2
路径长度为:10
从0到3的最短路径是:1<-3
路径长度为:4
从0到4的最短路径是:1<-3<-2<-4
路径长度为:14
从0到5的最短路径是:1<-3<-5
路径长度为:18
从1到2的最短路径是:2
路径长度为:9
从1到3的最短路径是:3
路径长度为:3
从1到4的最短路径是:3<-2<-4
路径长度为:14
从1到5的最短路径是:3<-5
路径长度为:18
从2到3的最短路径是:2<-3
路径长度为:12
从2到4的最短路径是:2<-4
路径长度为:14
从2到5的最短路径是:2<-3<-5
路径长度为:21
从3到4的最短路径是:4
路径长度为:13
从3到5的最短路径是:5
路径长度为:15
从4到5的最短路径是:5
路径长度为:4
```
阅读全文