采用Floyd算法求带权有向图的最短路径c语言
时间: 2024-03-28 22:31:43 浏览: 22
以下是使用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]; // 存储最短路径
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
dist[i][j] = 0; // 自己到自己的距离为0
} else {
dist[i][j] = INF; // 初始化为正无穷
}
}
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w); // 输入边的起点、终点和权值
dist[u][v] = w; // 存储边的权值
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; 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 = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d ", dist[i][j]); // 输出最短路径
}
printf("\n");
}
return 0;
}
```