Dijkstra算法详解（C语言实现最短路径的经典图论算法）

算法前提条件

• 图中所有边的权重必须为非负数（≥0）
• 适用于有向图或无向图
• 需要知道图的邻接表示（如邻接矩阵或邻接表）

C语言实现步骤

我们将使用邻接矩阵来表示图，并实现Dijkstra算法。以下是详细步骤：

1. 初始化：设置起点距离为0，其余为无穷大（用一个大数代替）
2. 创建一个数组记录每个顶点是否已确定最短路径
3. 重复以下操作，直到所有顶点都被处理：
   • 从未处理的顶点中选出当前距离最小的顶点 u
   • 标记 u 为已处理
   • 遍历 u 的所有邻居 v，如果通过 u 到 v 的路径更短，则更新 v 的距离

完整C语言代码实现

下面是一个完整的、可运行的C语言最短路径程序：

#include <stdio.h>#include <limits.h>// 图中顶点数量#define V 6int minDistance(int dist[], int sptSet[]) {    int min = INT_MAX, min_index;    for (int v = 0; v < V; v++)        if (sptSet[v] == 0 && dist[v] <= min)            min = dist[v], min_index = v;    return min_index;}void printSolution(int dist[]) {    printf("顶点\t距离起点的最短距离\n");    for (int i = 0; i < V; i++)        printf("%d \t\t %d\n", i, dist[i]);}void dijkstra(int graph[V][V], int src) {    int dist[V]; // 存储最短距离    int sptSet[V]; // sptSet[i] 为1表示顶点i已确定最短路径    // 初始化    for (int i = 0; i < V; i++) {        dist[i] = INT_MAX;        sptSet[i] = 0;    }    dist[src] = 0; // 起点到自己的距离为0    // 处理 V-1 个顶点    for (int count = 0; count < V - 1; count++) {        int u = minDistance(dist, sptSet);        sptSet[u] = 1;        // 更新u的所有邻居        for (int v = 0; v < V; v++)            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX                && dist[u] + graph[u][v] < dist[v])                dist[v] = dist[u] + graph[u][v];    }    printSolution(dist);}int main() {    // 示例图（邻接矩阵）    int graph[V][V] = {        {0, 4, 0, 0, 0, 0},        {4, 0, 8, 0, 0, 0},        {0, 8, 0, 7, 0, 4},        {0, 0, 7, 0, 9, 14},        {0, 0, 0, 9, 0, 10},        {0, 0, 4, 14, 10, 0}    };    dijkstra(graph, 0); // 从顶点0开始    return 0;}

代码说明

• minDistance()：从未确定最短路径的顶点中找出距离最小的
• dijkstra()：主函数，实现整个算法逻辑
• graph[V][V]：用邻接矩阵表示图，0表示无边，正整数表示边的权重
• 输出结果会显示从起点（本例为0）到每个顶点的最短距离

时间复杂度分析

上述实现的时间复杂度为 O(V²)，其中 V 是顶点数。如果使用优先队列（如二叉堆），可优化至 O((V + E) log V)，其中 E 是边数。但对于初学者，邻接矩阵版本更容易理解。

总结

通过本教程，你已经掌握了如何用C语言实现Dijkstra算法来解决最短路径问题。这是图论算法中的基石之一，广泛应用于地图导航、网络路由等领域。建议你动手运行代码，修改图的结构，观察输出变化，加深理解。

记住，学习Dijkstra算法的关键在于理解其“贪心”策略和逐步扩展的思想。祝你在算法学习之路上越走越远！