编辑代码

#include <stdio.h>
#define MAX_VEX 100  // 最大顶点数

// 创建图的邻接矩阵
int creatcost(int cost[][MAX_VEX]) {
    int vexnum, arcnum, i, j, k, v1, v2, w;
    printf("\n请输入顶点数和边数（输入格式为：顶点数,边数）：");
    scanf("%d,%d", &vexnum, &arcnum);
    
    // 初始化邻接矩阵
    for (i = 1; i <= vexnum; i++)
        for (j = 1; j <= vexnum; j++)
            cost[i][j] = 9999;  // 9999代表无限大
    
    // 输入边的信息
    for (k = 1; k <= arcnum; k++) {
        printf("请输入边的两个顶点及权重（格式：v1,v2,w）：");
        scanf("%d,%d,%d", &v1, &v2, &w);
        cost[v1][v2] = w;
        // 如果是无向图，取消下面这行的注释
        // cost[v2][v1] = w;
    }
    
    return vexnum;
}

// Dijkstra算法求从源点出发的最短路径
void dijkstra(int cost[][MAX_VEX], int vexnum) {
    int path[MAX_VEX], s[MAX_VEX], dist[MAX_VEX];
    int i, j, w, v, min, v1;
    
    printf("输入源点：");
    scanf("%d", &v1);  // 输入源点
    
    // 初始化
    for (i = 1; i <= vexnum; i++) {
        dist[i] = cost[v1][i];    // 初始距离
        s[i] = 0;                 // 所有顶点未加入S集合
        if (cost[v1][i] < 9999)
            path[i] = v1;         // 记录前驱顶点
    }
    
    s[v1] = 1;  // 源点加入S集合
    
    // 寻找最短路径
    for (i = 1; i <= vexnum; i++) {
        min = 9999;
        // 在S集合外寻找距离最小的顶点
        for (j = 1; j <= vexnum; j++) {
            if (s[j] == 0 && dist[j] < min) {
                min = dist[j];
                w = j;
            }
        }
        
        if (min == 9999) break;  // 剩余顶点不可达
        
        s[w] = 1;  // 将w加入S集合
        
        // 更新距离
        for (v = 1; v <= vexnum; v++) {
            if (s[v] == 0) {  // 只更新未加入S集合的顶点
                if (dist[w] + cost[w][v] < dist[v]) {
                    dist[v] = dist[w] + cost[w][v];
                    path[v] = w;  // 更新前驱顶点
                }
            }
        }
    }
    
    // 输出结果
    printf("\n源点 %d 到其他各顶点的路径与距离：\n", v1);
    for (i = 1; i <= vexnum; i++) {
        if (i != v1) {
            if (dist[i] != 9999) {
                printf("到顶点 %d 的最短路径: ", i);
                // 反向输出路径
                int temp = i;
                while (temp != v1) {
                    printf("%d <- ", temp);
                    temp = path[temp];
                }
                printf("%d", v1);
                printf("，总距离: %d\n", dist[i]);
            } else {
                printf("到顶点 %d 不可达\n", i);
            }
        }
    }
}

int main() {
    int cost[MAX_VEX][MAX_VEX];  // 邻接矩阵
    int vexnum;                  // 顶点数
    
    // 创建图
    vexnum = creatcost(cost);
    
    // 计算最短路径
    dijkstra(cost, vexnum);
    
    return 0;
}