迪杰斯特拉算法C程序实现最短路径

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找图中两点之间最短路径的算法，常用于解决单源最短路径问题。以下是迪杰斯特拉算法的C语言实现的基本步骤：

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

#define V 9 // 图的顶点数
#define INF INT_MAX

// 边的结构体表示
typedef struct {
    int src, dest, weight;
} Edge;

// 用于存储节点及其距离
typedef struct {
    int dist;
    int node;
} Node;

// 比较节点的距离
int compare(const void *a, const void *b) {
    return (*(Node *)a).dist - (*(Node *)b).dist;
}

// 迪杰斯特拉算法
void dijkstra(Edge edges[], int v, Node nodes[V]) {
    int i, u, minDistance;

    // 初始化所有节点为无限远，起点为0
    for (i = 0; i < V; i++)
        nodes[i].dist = INF;
    nodes[v].dist = 0;

    // 将所有节点加入优先队列
    qsort(nodes, V, sizeof(Node), compare);
    
    while (!IsEmpty(nodes)) { // 只有当队列不为空时
        u = nodes[0].node;
        nodes.dist = INF; // 将当前节点标记为已处理

        // 更新与其相邻节点的距离
        for (i = 0; i < edges[u].dest; i++) { // 假设每个顶点有一条边到下一个顶点
            if (nodes[edges[u].dest].dist > nodes[u].dist + edges[u].weight) {
                nodes[edges[u].dest].dist = nodes[u].dist + edges[u].weight;
                // 优先队列中的元素可能需要重新排序
                InsertionSort(nodes, edges[u].dest);
            }
        }
    }

    // 打印结果
    printf("Vertex \t\tDistance from Source\n");
    for (i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, nodes[i].dist);
}

// 辅助函数，判断队列是否为空
int IsEmpty(Node nodes[]) {
    return nodes.node == V;
}

// 辅助函数，对节点数组进行插入排序
void InsertionSort(Node nodes[], int k) {
    int i, j;
    Node temp;

    for (i = k; i > 0; i--) {
        if (nodes[i].dist > nodes[i - 1].dist) {
            temp = nodes[i];
            nodes[i] = nodes[i - 1];
            nodes[i - 1] = temp;
        }
    }
}

// 主函数调用
int main() {
    Edge edges[] = {{0, 1, 4}, {0, 7, 8}, {1, 2, 3}, {1, 6, 2}, {2, 3, 1}, {3, 4, 2}, {3, 5, 4}, {4, 6, 2}, {5, 6, 1}};
    int v = 0; // 源点

    Node nodes[V];

    dijkstra(edges, v, nodes);

    return 0;
}