C语言最短路径算法详解（Dijkstra算法从零入门到实战）

算法核心思想

Dijkstra算法采用贪心策略：

• 维护一个距离数组 dist[]，记录起点到每个顶点的当前最短距离。
• 初始时，起点距离为0，其余为无穷大（通常用一个极大值表示）。
• 每次从未确定最短路径的顶点中，选择距离最小的顶点，标记为“已确定”。
• 用该顶点更新其邻居的距离。
• 重复直到所有顶点都被处理。

C语言实现步骤

我们使用邻接矩阵来表示图。假设图有 V 个顶点（编号0到V-1）。

1. 定义常量和辅助函数

#define MAX_VERTICES 100#define INF 999999  // 表示无穷大// 找到未访问顶点中距离最小的int minDistance(int dist[], bool visited[], int V) {    int min = INF, min_index;    for (int v = 0; v < V; v++) {        if (!visited[v] && dist[v] <= min) {            min = dist[v];            min_index = v;        }    }    return min_index;}

2. Dijkstra主函数

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int V) {    int dist[MAX_VERTICES];     // 存储最短距离    bool visited[MAX_VERTICES]; // 记录是否已确定最短路径    // 初始化    for (int i = 0; i < V; i++) {        dist[i] = INF;        visited[i] = false;    }    dist[src] = 0; // 起点到自身距离为0    // 处理所有顶点    for (int count = 0; count < V - 1; count++) {        // 选择未访问且距离最小的顶点        int u = minDistance(dist, visited, V);        visited[u] = true;        // 更新u的所有邻居的距离        for (int v = 0; v < V; v++) {            if (!visited[v] &&                 graph[u][v] &&                 dist[u] != INF &&                 dist[u] + graph[u][v] < dist[v]) {                dist[v] = dist[u] + graph[u][v];            }        }    }    // 输出结果    printf("顶点\t距离\n");    for (int i = 0; i < V; i++) {        printf("%d \t %d\n", i, dist[i]);    }}

3. 主函数调用示例

#include <stdio.h>#include <stdbool.h>// ... 上面定义的函数 ...int main() {    int graph[MAX_VERTICES][MAX_VERTICES] = {        {0, 10, 0, 30, 100},        {0, 0, 50, 0, 0},        {0, 0, 0, 0, 10},        {0, 0, 20, 0, 60},        {0, 0, 0, 0, 0}    };    int V = 5; // 顶点数    int src = 0; // 起点    dijkstra(graph, src, V);    return 0;}

运行结果说明

以上代码以顶点0为起点，输出每个顶点到起点的最短距离。例如：

顶点    距离0       01       102       503       304       60

注意事项

• 该算法仅适用于非负权重的图。若存在负权边，请使用Bellman-Ford算法。
• 时间复杂度为 O(V²)，若使用优先队列（堆）优化，可降至 O((V + E) log V)。
• 本实现使用邻接矩阵，适合稠密图；稀疏图建议用邻接表。

总结

通过本教程，你已经掌握了如何用C语言实现Dijkstra最短路径算法。这是C语言图论编程的重要基础，也是面试和实际项目中的高频考点。多动手练习，尝试修改图结构或添加路径记录功能，你会对最短路径实现教程有更深理解！

希望这篇C语言最短路径算法教程对你有帮助！欢迎收藏并分享给需要的朋友。