C语言实现弗洛伊德算法

弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。下面是C语言实现弗洛伊德算法的代码：

#define Max_Int 32767
#define MAXV 100
typedef struct {
    char vex[MAXV];
    int edge[MAXV][MAXV];
    int vexnum, edgenum;
}AMGraph;
int D[MAXV][MAXV], path[MAXV][MAXV];
void CreateUDN(AMGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->edgenum);
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vex[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->edge[i][j] = Max_Int;
        }
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->edgenum; k++) {
        printf("请输入第%d条边的起点、终点和权值：", k + 1);
        scanf("%d%d%d", &i, &j, &w);
        G->edge[i][j] = w;
        G->edge[j][i] = w;
    }
}
void ShortestPath_Floyd(AMGraph G) {
    int i, j, k;
    for (i = 0; i < G.vexnum; i++) {
        for (j = 0; j < G.vexnum; j++) {
            D[i][j] = G.edge[i][j];
            path[i][j] = -1;
        }
    }
    for (k = 0; k < G.vexnum; k++) {
        for (i = 0; i < G.vexnum; i++) {
            for (j = 0; j < G.vexnum; j++) {
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}