在程序中直接导入加权无向图使用迪杰斯特拉算法求任意两点的最短路径及其最短值c语言代码

下面是使用 Dijkstra 算法求解加权无向图中任意两点的最短路径及其最短值的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAXVEX 100  // 最大顶点数
#define MAXWEIGHT INT_MAX  // 最大权重值

typedef struct {
    int vertex[MAXVEX];  // 顶点表
    int edge[MAXVEX][MAXVEX];  // 邻接矩阵
    int num_vex, num_edge;  // 图的当前顶点数和边数
} AdjMatrix;

void createGraph(AdjMatrix *G) {
    int i, j, k, weight;
    printf("请输入顶点数和边数: ");
    scanf("%d%d", &G->num_vex, &G->num_edge);
    getchar();  // 读取回车符
    printf("请输入顶点信息: ");
    for (i = 0; i < G->num_vex; i++) {
        scanf("%d", &G->vertex[i]);
    }
    getchar();  // 读取回车符
    for (i = 0; i < G->num_vex; i++) {
        for (j = 0; j < G->num_vex; j++) {
            G->edge[i][j] = MAXWEIGHT;  // 初始化邻接矩阵
        }
    }
    printf("请输入边信息(格式为: 起点 终点 权重):\n");
    for (k = 0; k < G->num_edge; k++) {
        scanf("%d%d%d", &i, &j, &weight);
        G->edge[i][j] = weight;
        G->edge[j][i] = weight;  // 无向图的邻接矩阵是对称的
    }
}

void printGraph(AdjMatrix *G) {
    int i, j;
    printf("顶点信息如下:\n");
    for (i = 0; i < G->num_vex; i++) {
        printf("%d ", G->vertex[i]);
    }
    printf("\n邻接矩阵信息如下:\n");
    for (i = 0; i < G->num_vex; i++) {
        for (j = 0; j < G->num_vex; j++) {
            if (G->edge[i][j] == MAXWEIGHT) {
                printf("∞ ");
            } else {
                printf("%d ", G->edge[i][j]);
            }
        }
        printf("\n");
    }
}

void Dijkstra(AdjMatrix *G, int start, int *dist, int *path) {
    bool visited[MAXVEX] = {false};
    int i, j, k, min_dist;
    for (i = 0; i < G->num_vex; i++) {
        dist[i] = G->edge[start][i];
        visited[i] = false;
        if (dist[i] == MAXWEIGHT) {
            path[i] = -1;
        } else {
            path[i] = start;
        }
    }
    dist[start] = 0;
    visited[start] = true;
    for (i = 1; i < G->num_vex; i++) {
        min_dist = MAXWEIGHT;
        for (j = 0; j < G->num_vex; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                k = j;
                min_dist = dist[j];
            }
        }
        visited[k] = true;
        for (j = 0; j < G->num_vex; j++) {
            if (!visited[j] && (min_dist + G->edge[k][j]) < dist[j]) {
                dist[j] = min_dist + G->edge[k][j];
                path[j] = k;
            }
        }
    }
}

void printPath(AdjMatrix *G, int start, int *dist, int *path) {
    int i, j, k;
    for (i = 0; i < G->num_vex; i++) {
        if (i != start) {
            printf("从顶点 %d 到顶点 %d 的最短路径为: ", start, i);
            printf("%d", i);
            j = i;
            while (path[j] != start) {
                printf("<--%d", path[j]);
                j = path[j];
            }
            printf("<--%d", start);
            printf(", 最短距离为: %d\n", dist[i]);
        }
    }
}

int main() {
    AdjMatrix G;
    int start, dist[MAXVEX], path[MAXVEX];
    createGraph(&G);
    printGraph(&G);
    printf("请输入起始顶点: ");
    scanf("%d", &start);
    Dijkstra(&G, start, dist, path);
    printPath(&G, start, dist, path);
    return 0;
}

在该示例代码中，我们定义了一个结构体 `AdjMatrix`，其中包含了顶点表和邻接矩阵。函数 `createGraph` 用来创建图，函数 `printGraph` 用来输出图的信息。在求解最短路径的过程中，我们使用了 Dijkstra 算法，其中 `Dijkstra` 函数用来计算从起始顶点到其他顶点的最短路径和最短距离，`printPath` 函数用来输出最短路径和最短距离。

需要注意的是，在初始化邻接矩阵时，我们将所有边的权重初始化为最大值，表示无穷大。在算法实现中，如果两个顶点之间没有边相连，则它们之间的距离也被认为是无穷大。