c语言实现Floyd算法,输入格式为节点的个数,边的个数,边的起点 边的终点 边的权值,要求输出弗洛伊德矩阵以及每两个点之间经过的节点
时间: 2024-05-01 11:19:02 浏览: 9
下面是C语言实现Floyd算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_NODES 100
int dist[MAX_NODES][MAX_NODES];
int path[MAX_NODES][MAX_NODES];
void floyd(int n) {
int i, j, k;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
path[i][j] = -1;
}
}
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
}
void print_path(int u, int v) {
if (path[u][v] == -1) {
printf("%d", v);
} else {
print_path(u, path[u][v]);
printf(" -> %d", v);
}
}
int main() {
int n, m, i, j, u, v, w;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = INT_MAX;
}
}
}
for (i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
dist[u][v] = w;
}
floyd(n);
printf("Floyd matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (dist[i][j] == INT_MAX) {
printf("INF ");
} else {
printf("%3d ", dist[i][j]);
}
}
printf("\n");
}
printf("Shortest path:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (i != j) {
printf("%d -> %d: ", i, j);
print_path(i, j);
printf("\n");
}
}
}
return 0;
}
```
输入格式为节点的个数和边的个数,接下来依次输入每条边的起点、终点和权值。程序会输出弗洛伊德矩阵以及每两个点之间经过的节点。
相关推荐
![](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)