#include <stdio.h>  
#include <string.h>  
#define MAX_NODE 5  // 节点数量（A,B,C,D,E）  
#define INF 10000   // 无穷大标记  

// 节点映射：0→A,1→B,2→C,3→D,4→E  
char nodeName[MAX_NODE] = {'A', 'B', 'C', 'D', 'E'};  

void dijkstra(int dist[MAX_NODE][MAX_NODE], int start) {  
    int shortest[MAX_NODE];       // 存储起点到各点的最短距离  
    int visited[MAX_NODE] = {0};  // 标记是否已确定最短路径  
    char path[MAX_NODE][50];      // 存储最短路径字符串  

    // 初始化  
    for (int i = 0; i < MAX_NODE; i++) {  
        shortest[i] = dist[start][i];  
        if (shortest[i] != INF) {  
            sprintf(path[i], "%c→%c", nodeName[start], nodeName[i]);  
        } else {  
            strcpy(path[i], "不可达");  
        }  
    }  
    visited[start] = 1;  // 起点标记为已确定  

    // 迭代确定其他节点的最短路径  
    for (int i = 0; i < MAX_NODE - 1; i++) {  
        // 找到未确定节点中距离起点最近的点  
        int minDist = INF, minIndex = -1;  
        for (int j = 0; j < MAX_NODE; j++) {  
            if (!visited[j] && shortest[j] < minDist) {  
                minDist = shortest[j];  
                minIndex = j;  
            }  
        }  
        if (minIndex == -1) break;  // 所有可达节点已处理  
        visited[minIndex] = 1;      // 标记为已确定  

        // 更新通过minIndex的路径距离  
        for (int j = 0; j < MAX_NODE; j++) {  
            if (!visited[j] && dist[minIndex][j] != INF &&  
                shortest[minIndex] + dist[minIndex][j] < shortest[j]) {  
                shortest[j] = shortest[minIndex] + dist[minIndex][j];  
                sprintf(path[j], "%s→%c", path[minIndex], nodeName[j]);  
            }  
        }  
    }  

    // 输出结果  
    printf("从起点%c出发的最短路径：\n", nodeName[start]);  
    for (int i = 0; i < MAX_NODE; i++) {  
        if (i != start) {  
            printf("到%c：距离=%d米，路径：%s\n",  
                   nodeName[i], shortest[i], path[i]);  
        }  
    }  
}  

int main() {  
    // 邻接矩阵：dist[i][j]表示i到j的距离（不可达为INF）  
    int dist[MAX_NODE][MAX_NODE] = {  
        {0, 10, 20, INF, INF},  
        {10, 0, 5, 15, INF},  
        {20, 5, 0, INF, 30},  
        {INF, 15, INF, 0, 5},  
        {INF, INF, 30, 5, 0}  
    };  
    dijkstra(dist, 0);  // 从A点（索引0）出发  
    return 0;  
}  
