迪杰斯特拉C语言代码实例

迪杰斯特拉算法是一种用于寻找图中最短路径的算法，通常用于解决单源最短路径问题。下面是一个简单的C语言迪杰斯特拉算法的代码示例，它假设输入图是一个邻接矩阵表示：

#include <stdio.h>
#include <stdlib.h>

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

int minDistance(int dist[], bool sptSet[]) {
    int min = INF, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V]; // 存储从src到各个顶点的距离
    bool sptSet[V]; // 标记数组，记录是否找到最短路径

    // 初始化距离数组和标记数组
    for (int i = 0; i < V; i++) {
        dist[i] = graph[src][i] != INF ? graph[src][i] : INF;
        sptSet[i] = false;
    }

    dist[src] = 0;

    // 主循环
    for (int count = 0; count < V - 1; count++) {
        // 找出未加入最短路径集合的最近顶点
        int u = minDistance(dist, sptSet);

        // 将该顶点加入最短路径集合
        sptSet[u] = true;

        // 更新所有邻居节点的距离
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != INF && dist[u] != INF + graph[u][v]) {
                dist[v] = min(dist[v], dist[u] + graph[u][v]);
            }
        }
    }

    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = { /* 邻接矩阵填充... */ }; // 填充实际的边权重
    int src = 0; // 起始顶点

    dijkstra(graph, src);
    return 0;
}

这个例子中，你需要替换`graph[V][V]`部分为实际的邻接矩阵，并指定起始顶点`src`。运行此程序会输出从起始顶点到其他顶点的最短距离。