迪杰斯特拉算法C语言代码

#include <stdio.h>
#include <stdlib.h>
#define Max_Int 32767
#define MVNum 100

typedef char VerTexType;
typedef int ArcType;

typedef struct {
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum, arcnum;
} AMGraph;

int D[MVNum];
int Path[MVNum];

void CreateUDN(AMGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = Max_Int;
        }
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条边的下标i,j和权值w：", k + 1);
        scanf("%d%d%d", &i, &j, &w);
        G->arcs[i][j] = w;
        G->arcs[j][i] = w;
    }
}

void ShortestPath_DIJ(AMGraph G, int v0) {
    int S[MVNum];
    int i, j, k, min;
    for (i = 0; i < G.vexnum; i++) {
        D[i] = G.arcs[v0][i];
        S[i] = 0;
        if (D[i] < Max_Int) {
            Path[i] = v0;
        } else {
            Path[i] = -1;
        }
    }
    D[v0] = 0;
    S[v0] = 1;
    for (i = 1; i < G.vexnum; i++) {
        min = Max_Int;
        for (j = 0; j < G.vexnum; j++) {
            if (S[j] == 0 && D[j] < min) {
                k = j;
                min = D[j];
            }
        }
        S[k] = 1;
        for (j = 0; j < G.vexnum; j++) {
            if (S[j] == 0 && D[k] + G.arcs[k][j] < D[j]) {
                D[j] = D[k] + G.arcs[k][j];
                Path[j] = k;
            }
        }
    }
}

int main(void) {
    int i, j;
    AMGraph G;
    CreateUDN(&G);
    ShortestPath_DIJ(G, 0);
    for (i = 1; i < G.vexnum; i++) {
        if (D[i] == Max_Int) {
            printf("0无法到达%c\n", G.vexs[i]);
        } else {
            printf("0到%c的权值为：%d\n", G.vexs[i], D[i]);
        }
    }
    return 0;
}