写一个C程序,运用Floyd算法求图的最短路径
时间: 2024-02-29 15:51:13 浏览: 35
好的,以下是实现Floyd算法求图的最短路径的C程序:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 图的最大顶点数
#define INF 0x7fffffff // 无穷大
typedef int VertexType; // 顶点的数据类型
typedef struct {
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 顶点数和边数
} MGraph;
void CreateMGraph(MGraph *G) { // 创建图的邻接矩阵
int i, j, k, w;
printf("请输入图的顶点数和边数:");
scanf("%d %d", &G->vexnum, &G->arcnum);
for (i = 0; i < G->vexnum; i++) { // 初始化邻接矩阵
for (j = 0; j < G->vexnum; j++) {
G->edges[i][j] = INF;
}
}
for (k = 0; k < G->arcnum; k++) { // 读入边的信息
printf("请输入第%d条边的起点、终点和权值:", k + 1);
scanf("%d %d %d", &i, &j, &w);
G->edges[i - 1][j - 1] = w;
G->edges[j - 1][i - 1] = w;
}
}
void Floyd(MGraph *G, int dist[][MAX_VERTEX_NUM]) { // Floyd算法求最短路径
int i, j, k;
for (i = 0; i < G->vexnum; i++) { // 初始化dist数组
for (j = 0; j < G->vexnum; j++) {
dist[i][j] = G->edges[i][j];
}
}
for (k = 0; k < G->vexnum; k++) { // 开始迭代
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
int main() {
MGraph G;
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM], i, j;
CreateMGraph(&G);
Floyd(&G, dist);
printf("图的最短路径矩阵为:\n");
for (i = 0; i < G.vexnum; i++) { // 输出最短路径矩阵
for (j = 0; j < G.vexnum; j++) {
printf("%d ", dist[i][j]);
}
printf("\n");
}
return 0;
}
```
程序中使用了邻接矩阵来存储图的信息,其中:
- `CreateMGraph` 函数用于创建图的邻接矩阵;
- `Floyd` 函数用于求最短路径;
- `dist` 数组存储的是任意两个顶点之间的最短路径。
需要注意的是,如果两个顶点之间没有边,那么它们之间的距离应该设为无穷大。在这里,我们使用了一个足够大的正整数来表示无穷大。