Dijkstra算法C语言实现难点是什么？-C语言-盈思创科技

算法思想简介：快速回顾 Dijkstra 算法是做什么的。
数据结构选择：解释我们将使用哪些 C 语言数据结构来表示图和辅助数据。
完整 C 语言代码：提供一份带有详细注释的、可直接运行的完整代码。
代码分步解析：对代码的关键部分进行详细解释。
算法复杂度分析：讨论该实现的时间复杂度和空间复杂度。
总结与扩展：总结要点并指出可以改进的方向。

算法思想简介

Dijkstra 算法用于在带权重的有向图或无向图中，寻找从单一源点到图中所有其他顶点的最短路径。

（图片来源网络，侵删）

其核心思想是贪心算法：

初始化：将源点到自身的距离设为 0，到其他所有顶点的距离设为无穷大（INT_MAX），将所有顶点标记为“未访问”。
选择：从未访问的顶点中，选出当前距离源点最近的那个顶点 u。
更新：对于 u 的每一个邻居 v，检查从源点经过 u 到达 v 的距离是否比当前已知的距离更短，如果是，则更新 v 的距离。
标记：将 u 标记为“已访问”。
重复：重复步骤 2、3、4,直到所有顶点都被访问过。

数据结构选择

为了高效地实现 Dijkstra 算法,我们需要选择合适的数据结构：

图：使用邻接矩阵 来表示，这是一个二维数组 graph[V][V]，graph[i][j] 存储从顶点 i 到顶点 j 的边的权重，如果两个顶点之间没有边，则权重为 0 或一个特殊值（如 INT_MAX），对于稀疏图（边数远小于 V²），邻接表会更高效,但邻接矩阵实现更简单直观。
距离数组：一个一维数组 dist[V],用来存储源点到每个顶点的当前最短距离估计。
已访问集合：一个一维布尔数组 sptSet[V]（shortest path tree set）,用来标记一个顶点是否已经找到了最短路径。
优先队列：这是算法效率的关键，我们需要一种能快速找到“当前距离最小的未访问顶点”的数据结构，在 C 语言中，标准库没有内置的优先队列，为了简化，我们可以使用线性扫描来找到最小值，但这会影响效率，下面的代码将采用这种简单方式,并在复杂度分析中讨论其影响。

完整 C 语言代码

这份代码实现了一个使用邻接矩阵的 Dijkstra 算法，它包含一个 main 函数来演示算法的使用。

#include <stdio.h>
#include <limits.h> // 用于 INT_MAX
#include <stdbool.h> // 用于 bool 类型
// 顶点数量
#define V 9
// 找到未访问顶点中距离最小的顶点的索引
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, 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 printSolution(int dist[]) {
    printf("顶点 \t\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]; // 输出数组，dist[i] 将保存从 src 到 i 的最短距离
    bool sptSet[V]; // sptSet[i] 为 true 如果顶点 i 已在最短路径树中或已找到最短路径
    // 1. 初始化距离数组和 sptSet 数组
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX; // 初始时，所有顶点距离为无穷大
        sptSet[i] = false; // 所有顶点都未访问
    }
    // 源点到自身的距离为 0
    dist[src] = 0;
    // 2. 遍历所有顶点
    for (int count = 0; count < V - 1; count++) {
        // 2.1 从未访问的顶点中选出距离最小的顶点 u
        int u = minDistance(dist, sptSet);
        // 2.2 标选出的顶点 u 为已访问
        sptSet[u] = true;
        // 2.3 更新 u 的所有邻居的距离
        // 对于每个顶点 v
        for (int v = 0; v < V; v++) {
            // 更新条件：
            // 1. sptSet[v] 为 false (顶点 v 未被访问)
            // 2. u 和 v 之间有边 (graph[u][v] 不为 0)
            // 3. 从 src 到 u 的距离 + u 到 v 的边权 < 当前从 src 到 v 的距离
            // 4. dist[u] 不是 INT_MAX，避免整数溢出
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    // 3. 打印最终计算出的最短距离
    printSolution(dist);
}
// 主函数，用于演示
int main() {
    /* 示例图，用邻接矩阵表示 */
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    printf("Dijkstra 算法计算从顶点 0 开始的最短路径:\n");
    dijkstra(graph, 0);
    return 0;
}

编译和运行

将以上代码保存为 dijkstra.c，然后使用 gcc 进行编译和运行：

（图片来源网络，侵删）

gcc dijkstra.c -o dijkstra
./dijkstra

预期输出

Dijkstra 算法计算从顶点 0 开始的最短路径:
顶点       从源点到该顶点的距离
0               0
1               4
2               12
3               19
4               21
5               11
6               9
7               8
8               14

代码分步解析

minDistance(int dist[], bool sptSet[])
- 这个函数是算法的“贪心”选择部分，它遍历所有顶点，检查哪些顶点还未被访问 (sptSet[v] == false)，然后在这些顶点中找到 dist 值最小的那个。
- 这个函数的时间复杂度是 O(V)，因为需要检查所有 V 个顶点。
dijkstra(int graph[V][V], int src)
- 初始化：for 循环将 dist 数组初始化为 INT_MAX，sptSet 初始化为 false，然后设置源点的距离 dist[src] = 0。
- 主循环：for (int count = 0; count < V - 1; count++) 这个循环执行 V-1 次，每次循环，我们都确定一个顶点的最短路径（除了最后一个顶点，它的路径在倒数第二次循环中就已确定）。
- 选择顶点：int u = minDistance(dist, sptSet); 调用上面的函数找到当前最近的未访问顶点 u。
- 标记顶点：sptSet[u] = true; 将 u 标记为已处理。
- 更新邻居距离：这是算法的核心，内层 for 循环遍历所有顶点 v，检查它们是否是 u 的邻居并且通过 u 可以获得更短的路径。
  - !sptSet[v]：确保 v 还没有被处理过。
  - graph[u][v]：确保 u 和 v 之间有边（权重不为0）。
  - dist[u] != INT_MAX：一个重要的边界条件，防止 dist[u] 是无穷大时与 graph[u][v] 相加导致整数溢出。
  - dist[u] + graph[u][v] < dist[v]：如果找到一条更短的路径，就更新 dist[v]。

算法复杂度分析

时间复杂度:
- 使用邻接矩阵:
  - minDistance 函数被调用 V 次，每次调用耗时 O(V)，所以这部分总时间是 O(V²)。
  - 更新邻居距离的嵌套循环，外层执行 V-1 次，内层执行 V 次，所以这部分总时间是 O(V²)。
  - 总时间复杂度为 O(V²)。
- 使用邻接表:
  - minDistance 函数仍然是 O(V²) 的瓶颈。
  - 如果用更高效的数据结构（如优先队列/最小堆）来代替 minDistance 函数，可以将查找最小顶点的复杂度从 O(V) 降到 O(log V)，总时间复杂度可以优化到 O(E log V)，E 是边的数量，对于稀疏图,这是一个巨大的提升。
空间复杂度:
（图片来源网络，侵删）
- 我们主要使用了 dist 和 sptSet 两个大小为 V 的数组。
- 图本身使用了一个 V x V 的邻接矩阵，空间为 O(V²)。
- 总空间复杂度为 O(V²)。

总结与扩展

这份 C 语言代码清晰地展示了 Dijkstra 算法的实现逻辑，它适用于带非负权重的图,并且使用邻接矩阵使其易于理解。
局限性：
- 无法处理负权重边：Dijkstra 算法的贪心策略在遇到负权重边时会失效，一个负权重的边可能会产生一条比当前“最短”路径更短的路径,但该算法不会回溯去检查。
- 效率问题：对于大规模稀疏图，O(V²) 的时间复杂度过高。
扩展与改进：
1. 使用优先队列：这是最重要的优化，可以用 C++ 的 priority_queue 或 C 语言自己实现一个最小堆来替换 minDistance 函数，将时间复杂度从 O(V²) 降低到 O(E log V)。
2. 处理负权重边：如果图中可能存在负权重边，应使用 Bellman-Ford 算法，Bellman-Ford 算法的时间复杂度为 O(V*E),并且可以检测图中是否存在负权重的环。
3. 输出路径：当前的代码只输出了最短路径的长度，如果我们想输出具体的路径，可以增加一个 parent 数组，在更新 dist[v] 的同时，记录 v 的前驱节点是 u，最后从目标节点回溯 parent 数组即可 reconstruct 路径。

Dijkstra算法C语言实现难点是什么？