C 语言实现Dijkstra算法 - 摩柯技术社区

Dijkstra算法概述

Dijkstra算法是由荷兰计算机科学家Edsger W. Dijkstra于1956年提出，并在1959年发表。它是一种用于在加权有向图中找到从给定源顶点到所有其他顶点的最短路径的算法。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法核心思想

Dijkstra算法基于贪心策略。它维护一个距离源点最近的顶点集合，每次从集合外选择距离源点最近的顶点加入集合，并更新该顶点邻接顶点到源点的距离。这个过程不断重复，直到所有顶点都被加入到集合中。

算法步骤

初始化：
- 将源点到自身的距离设为0，到其他所有顶点的距离设为无穷大（在代码实现中可以用一个很大的数表示）。
- 记录源点到每个顶点的最短路径前驱顶点，初始时都设为 -1，表示无前驱。
- 标记所有顶点为未访问。
选择最小距离顶点：
- 在所有未访问的顶点中，选择距离源点最近的顶点。
更新邻接顶点距离：
- 对于所选顶点的每个邻接顶点，如果通过当前顶点到达邻接顶点的距离比已知的距离更短，则更新邻接顶点到源点的距离，并记录当前顶点为其前驱顶点。
标记顶点为已访问：
- 将所选顶点标记为已访问。
重复：
- 重复步骤2到4，直到所有顶点都被访问。

C语言实现Dijkstra算法

数据结构定义

#include <stdio.h>
#include <limits.h>
#define V 9 // 顶点数量

// 图的邻接表表示法，这里使用邻接矩阵简单实现
typedef struct Graph {
    int adjMatrix[V][V];
} Graph;

// 初始化图
void initGraph(Graph *g) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph *g, int src, int dest, int weight) {
    g->adjMatrix[src][dest] = weight;
    // 如果是无向图，还需要添加反向边
    // g->adjMatrix[dest][src] = weight;
}

在上述代码中，首先定义了一个 Graph 结构体来表示图，使用邻接矩阵 adjMatrix 存储图的边信息。initGraph 函数用于初始化邻接矩阵，将所有元素设为0。addEdge 函数用于向图中添加边，这里实现的是有向图，如果是无向图，需要同时添加反向边。

Dijkstra算法实现

// 找到距离源点最近的未访问顶点
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }

    return minIndex;
}

// 打印从源点到各顶点的最短路径
void printPath(int parent[], int j) {
    if (parent[j] == -1) {
        printf("%d ", j);
        return;
    }
    printPath(parent, parent[j]);
    printf("%d ", j);
}

// 打印从源点到各顶点的距离和路径
void printSolution(int dist[], int parent[], int src) {
    printf("Vertex \t Distance \t Path\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d \t\t %d ", i, dist[i], src);
        printPath(parent, i);
        printf("\n");
    }
}

// Dijkstra算法主函数
void dijkstra(Graph *g, int src) {
    int dist[V];
    int sptSet[V];
    int parent[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
        parent[i] = -1;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && g->adjMatrix[u][v] && dist[u] != INT_MAX && dist[u] + g->adjMatrix[u][v] < dist[v]) {
                dist[v] = dist[u] + g->adjMatrix[u][v];
                parent[v] = u;
            }
        }
    }

    printSolution(dist, parent, src);
}

在这段代码中，minDistance 函数用于在所有未访问顶点中找到距离源点最近的顶点。printPath 函数通过递归方式打印从源点到指定顶点的最短路径。printSolution 函数用于打印从源点到各个顶点的距离和路径。dijkstra 函数是Dijkstra算法的核心实现，它初始化距离数组 dist、访问标记数组 sptSet 和前驱顶点数组 parent，然后通过循环不断选择距离源点最近的未访问顶点，并更新其邻接顶点的距离和前驱顶点，最后调用 printSolution 函数输出结果。

主函数及测试

int main() {
    Graph g;
    initGraph(&g);

    addEdge(&g, 0, 1, 4);
    addEdge(&g, 0, 7, 8);
    addEdge(&g, 1, 2, 8);
    addEdge(&g, 1, 7, 11);
    addEdge(&g, 2, 3, 7);
    addEdge(&g, 2, 8, 2);
    addEdge(&g, 2, 5, 4);
    addEdge(&g, 3, 4, 9);
    addEdge(&g, 3, 5, 14);
    addEdge(&g, 4, 5, 10);
    addEdge(&g, 5, 6, 2);
    addEdge(&g, 6, 7, 1);
    addEdge(&g, 6, 8, 6);
    addEdge(&g, 7, 8, 7);

    dijkstra(&g, 0);

    return 0;
}

在 main 函数中，首先初始化图 g，然后添加一些边来构建一个示例图。最后调用 dijkstra 函数，以顶点0为源点计算最短路径，并输出结果。

算法复杂度分析

时间复杂度

朴素实现：
- 在朴素的Dijkstra算法实现中，每次从所有未访问顶点中选择距离源点最近的顶点，这个操作需要遍历所有未访问顶点，时间复杂度为 (O(V))。而整个算法需要进行 (V - 1) 次这样的选择操作，同时每次选择后更新邻接顶点距离的操作时间复杂度为 (O(E))（其中 (E) 是边的数量）。因此，朴素Dijkstra算法的时间复杂度为 (O(V^2 + E))。在稠密图（边的数量接近 (V^2)）的情况下，时间复杂度近似为 (O(V^2))。
使用优先队列优化：
- 如果使用优先队列（如最小堆）来存储未访问顶点及其距离，每次选择距离源点最近的顶点（即堆顶元素）的时间复杂度降为 (O(\log V))，每次更新邻接顶点距离（即调整堆）的时间复杂度也为 (O(\log V))。由于需要进行 (V - 1) 次选择操作和 (E) 次更新操作，所以使用优先队列优化后的Dijkstra算法时间复杂度为 (O((V + E)\log V))。在稀疏图（边的数量远小于 (V^2)）的情况下，这种优化效果显著。

空间复杂度

存储图的空间：
- 使用邻接矩阵存储图时，空间复杂度为 (O(V^2))，因为邻接矩阵是一个 (V \times V) 的二维数组。
- 如果使用邻接表存储图，空间复杂度为 (O(V + E))，因为需要存储 (V) 个顶点的表头和 (E) 条边的信息。
算法辅助空间：
- 算法中需要额外的数组来存储距离（dist）、访问标记（sptSet）和前驱顶点（parent），这些数组的大小都为 (V)，所以辅助空间复杂度为 (O(V))。综合起来，朴素实现下总的空间复杂度在使用邻接矩阵时为 (O(V^2))，使用邻接表时为 (O(V + E))。使用优先队列优化时，优先队列中最多存储 (V) 个元素，所以空间复杂度仍为 (O(V))，整体空间复杂度在使用邻接矩阵时仍为 (O(V^2))，使用邻接表时为 (O(V + E))。

应用场景

网络路由：在计算机网络中，Dijkstra算法可用于确定数据包从源节点到目的节点的最短路径。路由器可以使用该算法来计算最佳的转发路径，以优化网络流量，减少延迟。
地图导航：地图应用中，为了找到两点之间的最短路线，Dijkstra算法可以在地图的道路网络（图结构）上计算出最优路径。例如，在城市道路图中，顶点可以表示交叉路口，边表示道路，边的权重可以表示道路的长度或预计行驶时间。
电信网络：在电信网络中，Dijkstra算法可用于确定信号传输的最短路径，以优化网络资源的使用，确保通信的高效性和稳定性。
物流配送：物流公司在规划配送路线时，可以使用Dijkstra算法来找到从仓库到各个送货地点的最短路径，从而节省运输成本和时间。

算法局限性

负权边问题：Dijkstra算法基于贪心策略，它假设一旦一个顶点被确定为距离源点最近并加入到已访问集合中，其距离就不会再改变。然而，当图中存在负权边时，这个假设就不成立了。如果存在负权边，后续可能会发现通过负权边可以得到更短的路径，从而导致Dijkstra算法计算出的路径不一定是真正的最短路径。例如，在一个包含负权环（所有边权之和为负的环）的图中，Dijkstra算法可能会陷入无限循环或者给出错误的结果。解决负权边问题通常需要使用Bellman - Ford算法等其他专门处理负权边的算法。
计算复杂度：虽然在某些情况下（如稀疏图使用优先队列优化）Dijkstra算法表现良好，但在大规模图（顶点和边数量非常大）的情况下，其时间复杂度仍然较高。即使使用优先队列优化，对于非常密集的图，其时间复杂度 (O((V + E)\log V)) 也可能变得难以接受。在这种情况下，可能需要考虑更高效的近似算法或者分布式计算方法来解决最短路径问题。

通过以上对Dijkstra算法的详细介绍、C语言实现、复杂度分析、应用场景及局限性的阐述，希望读者对该算法有更深入的理解，并能够在实际项目中灵活运用。