floyd算法c语言
时间: 2023-10-20 19:00:18 浏览: 119
Floyd算法是一种用于解决图中最短路径问题的算法,它可以到图中任意两个节点之间的最短路径。下面是一个使用C语言实现Floyd算法的示例代码:
```c
#include <stdio.h>
#define INF 99999
#define V 4
void floydWarshall(int graph[V][V]) {
int dist[V][V];
int i, j, k;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; 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 < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] == INF) {
printf("%7s", "INF");
} else {
printf("%7d", dist[i][j]);
}
}
printf("\n");
}
}
int main() {
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}
```
这段代码演示了一个包含4个节点的图的最短路径计算。请注意,INF代表两个节点之间没有直接连接的路径。运行代码后,将输出最短路径矩阵,其中每个元素表示从一个节点到另一个节点的最短路径长度。
阅读全文