floyd算法求无向图的最短路径并输出最短路径及其长度c语言
时间: 2024-02-06 19:10:18 浏览: 28
以下是C语言实现Floyd算法求解无向图最短路径及其长度的示例代码:
```c
#include <stdio.h>
#define INF 0x3f3f3f3f // 无穷大
int main()
{
int n, m;
scanf("%d %d", &n, &m); // 输入结点数和边数
int dist[n+1][n+1]; // 存储结点间距离
memset(dist, INF, sizeof(dist)); // 初始化为无穷大
for(int i = 1; i <= n; i++)
dist[i][i] = 0; // 自身到自身的距离为0
int u, v, w;
for(int i = 1; i <= m; i++)
{
scanf("%d %d %d", &u, &v, &w); // 输入边的起点、终点和权值
dist[u][v] = w;
dist[v][u] = w; // 无向图需要双向存储
}
// Floyd算法求解最短路径
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][j] > dist[i][k] + dist[k][j])
dist[i][j] = dist[i][k] + dist[k][j];
// 输出最短路径及其长度
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++)
printf("%d 到 %d 的最短路径为 %d,路径长度为 %d\n", i, j, j, dist[i][j]);
return 0;
}
```
在输入时,需要按照以下格式输入:
- 第一行为结点数n和边数m,用空格分隔;
- 接下来m行每行为一条边的起点u、终点v和权值w,用空格分隔。
例如,以下是一个包含5个结点和7条边的无向图的输入示例:
```
5 7
1 2 2
1 3 4
2 3 1
2 4 7
3 4 3
3 5 6
4 5 5
```
输出结果如下:
```
1 到 2 的最短路径为 2,路径长度为 2
1 到 3 的最短路径为 3,路径长度为 4
1 到 4 的最短路径为 3,路径长度为 10
1 到 5 的最短路径为 4,路径长度为 9
2 到 3 的最短路径为 3,路径长度为 1
2 到 4 的最短路径为 4,路径长度为 8
2 到 5 的最短路径为 3,路径长度为 7
3 到 4 的最短路径为 3,路径长度为 3
3 到 5 的最短路径为 3,路径长度为 6
4 到 5 的最短路径为 5,路径长度为 5
```