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

void dijkstra(int n, int graph[n][n], int source, int dist[n], int parent[n], bool visited[n]) { 
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;  // 初始距离为无穷大
        parent[i] = -1;  // 前驱节点初始化为 -1
        visited[i] = false;  // 所有节点初始未访问
    }
    dist[source] = 0;  // 源节点的距离为 0
    for (int i = 0; i < n - 1; i++) {// 寻找未访问的最小距离节点        
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;// 标记节点 u 为已访问
        // 更新与节点 u 相邻的未访问节点的最短路径
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;  // 更新前驱节点
            }
        }
    }
}
void printPath(int parent[], int node) {
    if (node == -1) return;  // 终止条件
    printPath(parent, parent[node]);  // 递归打印前驱节点
    printf("%d ", node);  // 打印当前节点
}  
// 主函数
int main() {
    int n = 5;
    int graph[5][5] = { // 邻接矩阵表示图
        {0, 10, INT_MAX, INT_MAX, 5},
        {10, 0, 1, INT_MAX, INT_MAX},
        {INT_MAX, 1, 0, 3, INT_MAX},
        {INT_MAX, INT_MAX, 3, 0, 8},
        {5, INT_MAX, INT_MAX, 8, 0}
    };
    int source = 0;  // 设定源节点为 0
    int dist[n];  // 存储到每个节点的最短距离
    int parent[n];  // 存储每个节点的前驱节点
    bool visited[n];  // 标记节点是否已经访问
    // 运行 Dijkstra 算法
    dijkstra(n, graph, source, dist, parent, visited);
    // 输出最短路径结果
    for (int i = 1; i < n; i++) {
        if (dist[i] == INT_MAX) {
            printf("到点 %d 不可直达.\n", i);
        } else {
            printf("源点到%d的最短路径是 %d，路径为: ", i, dist[i]);
            printPath(parent, i);  // 打印路径
            printf("\n");
        }
    } 
    return 0;
}