c语言单源最短路径的贪心算法代码

以下是C语言单源最短路径的贪心算法代码：

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

#define MAX_SIZE 100

int n; // 图中节点数
float a[MAX_SIZE][MAX_SIZE]; // 图的邻接矩阵
float dist[MAX_SIZE]; // 存储源点到各个节点的最短距离
int prev[MAX_SIZE]; // 存储最短路径上各个节点的前驱节点

void dijkstra(int s) {
    int i, j, u;
    float min;
    int visited[MAX_SIZE] = {0}; // 标记节点是否已被访问

    // 初始化
    for (i = 0; i < n; i++) {
        dist[i] = a[s][i];
        visited[i] = 0;
        if (dist[i] == INT_MAX) {
            prev[i] = -1;
        } else {
            prev[i] = s;
        }
    }
    dist[s] = 0;
    visited[s] = 1;

    // 迭代n-1次
    for (i = 1; i < n; i++) {
        min = INT_MAX;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                u = j;
                min = dist[j];
            }
        }
        visited[u] = 1;
        for (j = 0; j < n; j++) {
            if (!visited[j] && a[u][j] < INT_MAX) {
                if (dist[u] + a[u][j] < dist[j]) {
                    dist[j] = dist[u] + a[u][j];
                    prev[j] = u;
                }
            }
        }
    }
}

int main() {
    int i, j;
    int s = 0; // 源点

    // 读入图的邻接矩阵
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%f", &a[i][j]);
            if (a[i][j] == -1) {
                a[i][j] = INT_MAX;
            }
        }
    }

    // 计算最短路径
    dijkstra(s);

    // 输出结果
    for (i = 0; i < n; i++) {
        printf("从%d到%d的最短距离为：%f，路径为：", s, i, dist[i]);
        j = i;
        while (prev[j] != -1) {
            printf("%d ", j);
            j = prev[j];
        }
        printf("%d\n", j);
    }

    return 0;
}