#include <stdio.h>
#include <float.h>
#include <stdbool.h>
#define MAX_NODES 5
void dijkstra(int v, float a[MAX_NODES][MAX_NODES], 
                float dist[MAX_NODES], int prev[MAX_NODES]) {
    int n = MAX_NODES;  // 节点总数
    if (v < 0 || v >= n) {  return;  // 如果源节点不在有效范围内，返回
    }
    bool s[MAX_NODES] = {false};  // 标记节点是否已确定最短路径   
    for (int i = 0; i < n; i++) { // 初始化
        dist[i] = a[v][i];      s[i] = false;
        if (dist[i] == FLT_MAX) {  prev[i] = -1;  // 如果没有路径，prev 设置为 -1
        } else {   prev[i] = v;   // 否则，前驱节点为源节点  
         }
    }
    dist[v] = 0;  // 源节点的距离是0
    s[v] = true;  // 源节点加入已确定集合   
    for (int i = 1; i < n; i++) { // Dijkstra 算法主体
        float temp = FLT_MAX;   int u = v;
        // 选择未访问的最短路径节点
        for (int j = 0; j < n; j++) {
            if (!s[j] && dist[j] < temp) {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = true;  // 确定最短路径节点 u
        // 更新与节点 u 相邻的节点的最短路径
        for (int j = 0; j < n; j++) {
            if (!s[j] && a[u][j] < FLT_MAX) {
                float newdist = dist[u] + a[u][j];
                if (newdist < dist[j]) {
                    dist[j] = newdist;
                    prev[j] = u;  // 更新前驱节点
                }
            }
        }
    }
}
int main() {
    // 定义图的邻接矩阵 (FLT_MAX 表示没有路径)
    float a[MAX_NODES][MAX_NODES] = {
        {0, 8, 1, 2, FLT_MAX},
        {8, 0, FLT_MAX, 3, FLT_MAX},
        {1, FLT_MAX, 0, 2, 3},
        {2, 3, 2, 0, 3},
        {FLT_MAX, FLT_MAX, 3, 3, 0}
    };
    float dist[MAX_NODES];  // 存储从源点到各个节点的最短距离
    int prev[MAX_NODES];    // 存储每个节点的前驱节点
    // 执行 Dijkstra 算法，从节点 0 开始
    dijkstra(0, a, dist, prev);
    // 输出源点到其他节点的最短距离
    for (int i = 1; i < MAX_NODES; i++) {
        if (dist[i] == FLT_MAX) {
            printf("源点到%d没有路径\n", i);
        } else {
            printf("源点到%d的最短距离为：%.2f\n", i, dist[i]);
        }
    }
    return 0;
}