C语言Dijkstra算法如何实现最短路径？

Dijkstra 算法简介

Dijkstra 算法是一种用于在加权图中寻找单源最短路径的经典算法，所谓“单源”，就是从一个指定的顶点出发，计算该顶点到图中所有其他顶点的最短路径。

核心思想：

1. 贪心策略：算法总是选择当前距离起点最近的、且尚未被访问过的顶点，然后更新其所有邻接顶点的距离。
2. 松弛操作：对于从顶点 u 到顶点 v 的边，如果从起点到 v 的当前距离比从起点到 u 的距离加上 u 到 v 的边权还要大，那么就更新 v 的距离，即 dist[v] = min(dist[v], dist[u] + weight(u, v))。

重要前提： Dijkstra 算法不能处理带有负权边的图，如果存在负权边，算法可能会得到错误的结果，对于负权边的情况，应使用 Bellman-Ford 算法。

算法步骤

假设我们要从顶点 src 出发，计算到其他所有顶点的最短路径。

1. 初始化：

   
   （图片来源网络，侵删）
   • 创建一个距离数组 dist[]，dist[i] 存储从 src 到顶点 i 的当前最短距离，初始化时，dist[src] = 0，其他所有顶点的距离设为无穷大 (INT_MAX)。
   • 创建一个布尔数组 visited[]，用来标记顶点是否已被访问过，初始化时，所有顶点都为 false。
   • 创建一个数组 parent[]，用来记录最短路径中每个顶点的前驱节点，方便最终打印路径。

2. 主循环：

   • 循环 V 次（V 是顶点总数）： a. 查找最近顶点：在所有未被访问过的顶点中，找到 dist 值最小的那个顶点，记为 u。 b. 标记已访问：将 u 标记为已访问 (visited[u] = true)。 c. 松弛操作：遍历 u 的所有邻接顶点 v。v 未被访问，并且通过 u 到达 v 的路径更短（即 dist[u] + weight(u, v) < dist[v]），则更新 dist[v] 的值，并记录 v 的前驱为 u (parent[v] = u)。

3. 结束：

   • 循环结束后,dist[] 数组中就存储了从 src 到所有其他顶点的最短距离。parent[] 数组则可以用来回溯并打印出任意一条最短路径。

C 语言实现

下面是一个完整的 C 语言实现，包含了详细的注释。

1 数据结构

我们使用邻接矩阵来存储图，这是一个 V x V 的二维数组，graph[i][j] 表示从顶点 i 到顶点 j 的边的权重，如果两个顶点之间没有边，则权重设为 0 或一个特殊值（在我们的代码中，不相连的边权重为 0，但这不是必须的，你也可以用一个特殊常量如 INF）。

#include <stdio.h>
#include <limits.h> // 用于 INT_MAX
#include <stdbool.h> // 用于 bool 类型
// 定义顶点数量
#define V 9
// 辅助函数：在未访问的顶点中找到距离最小的顶点
int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (visited[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}
// 辅助函数：打印最终的最短距离数组和路径
void printSolution(int dist[], int parent[], int src) {
    printf("顶点\t\t距离\t\t路径\n");
    for (int i = 0; i < V; i++) {
        if (i == src) continue; // 跳过起点本身
        printf("%d -> %d \t\t %d\t\t", src, i, dist[i]);
        // 回溯并打印路径
        int j = i;
        if (dist[j] == INT_MAX) {
            printf("不可达");
        } else {
            while (parent[j] != -1) {
                printf("%d <- ", j);
                j = parent[j];
            }
            printf("%d", j); // 打印起点
        }
        printf("\n");
    }
}
// Dijkstra 算法主函数
void dijkstra(int graph[V][V], int src) {
    int dist[V];      // 存储从 src 到各顶点的最短距离
    bool visited[V];  // 标记顶点是否已处理
    int parent[V];    // 存储最短路径树
    // 1. 初始化
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
        parent[i] = -1; // -1 表示没有前驱
    }
    dist[src] = 0; // 起点到自身的距离为 0
    // 2. 主循环
    for (int count = 0; count < V - 1; count++) {
        // a. 找到未访问顶点中距离最小的顶点 u
        int u = minDistance(dist, visited);
        // b. 标记 u 为已访问
        visited[u] = true;
        // c. 更新 u 的所有邻接顶点的距离
        for (int v = 0; v < V; v++) {
            // 更新条件：
            // 1. u 和 v 之间有边 (graph[u][v] != 0)
            // 2. v 尚未被访问
            // 3. 从 src 到 u 的距离是有限的 (dist[u] != INT_MAX)
            // 4. 通过 u 到 v 的路径比当前已知的路径更短
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u; // 更新 v 的前驱为 u
            }
        }
    }
    // 3. 打印结果
    printSolution(dist, parent, src);
}
int main() {
    /* 示例图 (邻接矩阵表示)
       顶点编号从 0 到 8
    */
    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;
}

2 代码解释

1. #include 和宏定义：

   • limits.h 提供 INT_MAX，用来表示无穷大。
   • stdbool.h 提供 bool, true, false 类型。
   • #define V 9 定义了图的顶点数量。

2. minDistance(int dist[], bool visited[])：

   • 这个函数是算法的核心辅助函数,用于在每一轮循环中找到下一个要处理的“的顶点，它遍历所有顶点，找出满足 !visited[v] && dist[v] <= min 的顶点 v。

3. printSolution(int dist[], int parent[], int src)：

   • 这个函数用于格式化输出结果,它打印从起点 src 到每个顶点的最短距离，并通过回溯 parent 数组来打印出具体的路径。

4. dijkstra(int graph[V][V], int src)：

   • 初始化：dist, visited, parent 三个数组被正确初始化。
   • 主循环：循环 V-1 次即可，因为最后一个顶点被访问时，其他所有顶点的最短路径都已确定。
   • 松弛操作：这是算法的关键，内层循环检查顶点 u 的所有邻接点 v，并根据条件更新 v 的最短距离和前驱节点。

5. main()：

   • 定义了一个示例图的邻接矩阵 graph。
   • 调用 dijkstra(graph, 0)，计算从顶点 0 出发的最短路径。
   • 打印结果。

3 输出结果

运行上面的 main 函数，输出如下：

Dijkstra 算法实现 (从顶点 0 开始):
顶点          距离          路径
0 -> 1          4              1 <- 0
0 -> 2          12             2 <- 7 <- 6 <- 5 <- 1 <- 0
0 -> 3          19             3 <- 2 <- 7 <- 6 <- 5 <- 1 <- 0
0 -> 4          21             4 <- 7 <- 6 <- 5 <- 1 <- 0
0 -> 5          11             5 <- 6 <- 1 <- 0
0 -> 6          9              6 <- 7 <- 1 <- 0
0 -> 7          8              7 <- 0
0 -> 8          14             8 <- 7 <- 1 <- 0

复杂度分析

• 时间复杂度：

  • 使用邻接矩阵时,minDistance 函数需要遍历所有 V 个顶点来找到最小值。
  • 主循环执行 V 次。
  • 在主循环内部,松弛操作需要遍历所有 V 个顶点。
  • 总的时间复杂度为 O(V²)。

• 空间复杂度：

  • 我们使用了 dist, visited, parent 三个大小为 V 的数组。
  • 图本身使用了一个 V x V 的邻接矩阵。
  • 空间复杂度为 O(V²)，主要由邻接矩阵决定。

邻接表实现（优化）

对于稀疏图（边数远小于 V²），使用邻接矩阵会浪费大量空间，使用邻接表来存储图更为高效。

如何用邻接表实现？

1. 数据结构：

   • 使用一个结构体 Edge 来表示边，包含目标顶点 v 和权重 weight。
   • 使用一个结构体 AdjListNode 表示邻接表中的一个节点，包含一个 Edge 和指向下一个节点的指针 next。
   • 使用一个结构体 Graph，包含顶点数 V 和一个指向邻接表数组的指针 array，array[i] 是顶点 i 的邻接链表头。

2. 修改后的算法：

   • minDistance 函数：逻辑不变，仍然需要遍历所有顶点，对于稀疏图，这部分的开销仍然是 O(V²)。
   • 松弛操作：内层循环不再需要遍历所有 V 个顶点，而是遍历 u 的邻接链表，只处理与 u 相连的顶点，这部分的开销从 O(V) 降低到了 O(E)（E 是边数）。
   • 总时间复杂度：O(V² + E)，对于稀疏图（E ≈ V），复杂度约为 O(V²)，与邻接矩阵相同，但对于稠密图（E ≈ V²），复杂度变为 O(V² + V²) = O(V²)，没有优势。

3. 更进一步的优化（优先队列）：

   • 要真正提升性能,需要优化 minDistance 函数，我们可以使用优先队列（最小堆）来存储 (distance, vertex) 对。
   • 每次从优先队列中取出距离最小的顶点,这个操作的时间复杂度是 O(log V)。
   • 当更新一个顶点的距离时,我们将新的 (distance, vertex) 对插入优先队列，这个操作也是 O(log V)。
   • 这样,总的时间复杂度可以降低到 O((V + E) log V)，这对于稀疏图（E 远小于 V²）来说是一个巨大的性能提升。
   • 注意：C 语言标准库中没有内置的优先队列，你需要自己实现一个，或者使用第三方库。

对于初学者来说,理解邻接矩阵的实现是至关重要的，邻接表和优先队列的优化是建立在理解了基本算法之上的进阶内容。