C语言最短路径算法详解（Dijkstra算法从零实现）

算法核心思想

• 维护一个距离数组 dist[]，记录起点到每个节点的当前最短距离。
• 使用一个集合（或布尔数组）记录哪些节点的最短路径已经确定。
• 每次从未确定最短路径的节点中选择距离最小的节点，用它来更新其邻居的距离。
• 重复此过程，直到所有节点都被处理。

C语言实现步骤

我们将用邻接矩阵表示图，并实现Dijkstra算法。以下是完整代码：

#include <stdio.h>#include <limits.h>#define V 6  // 图中顶点数量// 找到距离最小且未处理的顶点int 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]);}// Dijkstra算法主函数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() {    // 示例图的邻接矩阵（0表示无边）    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;}

代码解析

上述代码实现了完整的C语言图论编程流程：

• minDistance 函数用于查找未处理节点中距离最小的节点。
• dijkstra 函数是核心逻辑，初始化距离数组后，循环处理每个节点。
• 邻接矩阵 graph 表示图的连接关系和边权重。
• 最终输出从起点（本例为0）到所有其他顶点的最短距离。

注意事项

Dijkstra算法要求图中不能有负权边。如果存在负权边，应考虑使用Bellman-Ford算法。此外，该实现的时间复杂度为 O(V²)，适用于顶点数不大的场景；若图稀疏，可结合优先队列优化至 O(E log V)。

总结

通过本文，你已经掌握了如何用C语言实现最短路径实现的核心方法——Dijkstra算法。这不仅加深了你对图论的理解，也为后续学习更复杂的网络算法打下坚实基础。动手运行代码，修改图结构，观察输出变化，是掌握C语言最短路径算法的最佳方式！