Blog of CIU

Dijkstra 算法

6 min read

Dijkstra 算法解决 单源最短路径 问题：给定带权有向图与起点 ，求 到每个顶点的最短距离。要求边权 非负；若存在负权边，应改用 Bellman-Ford。

本仓库提供两种实现——朴素选点法 与 优先队列（小根堆）法，示例图相同，结果一致。

特性：朴素版时间 · 堆优化 · 仅适用于非负权图

源码：朴素实现 (C)、优先队列实现 (C++)

示例图

两份实现使用同一张图便于对比：

1 -2-> 2 -1-> 3
1 -5-> 3

边集：（权 2）、（权 5）、（权 1）。从 1 到 3 的最短路径为 ，距离为 3。

公共思路

两种实现共享同一贪心框架：

  1. 维护 dis[]：当前已知的从起点到各顶点的最短距离，初始 dis[s] = 0，其余为 。
  2. 每次 确定 一个尚未处理、且 dis 最小的顶点 （即「当前最近且未定型」的顶点）。
  3. 松弛 的出边：对每个邻居 ，想一想「先到 （已是最短），再走 这条边」会不会更近；若 dis[u] + w 比当前 dis[v] 更小，就把 dis[v] 改成这个更短的距离。
  4. 重复直到所有可达顶点都被定型。

区别在于第 2 步如何找 ：朴素版线性扫描全部顶点；堆优化版用小根堆按 dis 取最小。

朴素实现（C）

邻接表

typedef struct Edge {
    int v, w;
    struct Edge* next;
} Edge;
 
Edge* G[maxn];

建边时将新边头插到 G[u]，与拓扑排序等 C 实现风格一致。

核心代码

用 vis[] 标记已定型顶点；每轮在未访问顶点中线性找 dis 最小者：

void dijkstra(int s, int n) {
    memset(dis, inf, (n + 1) * sizeof(int));
    dis[s] = 0;
 
    for (int i = 1; i <= n; i++) {  // 共定型 n 个顶点
        // 1. 在未定型顶点中找 dis 最小者
        int u = 0, mind = inf;
 
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < mind) {
                u = j;
                mind = dis[j];
            }
        }
 
        vis[u] = 1;  // 定型：此后 dis[u] 不再变化
 
        // 2. 绕道 u 尝试缩短到各邻居的距离
        for (Edge* e = G[u]; e; e = e->next) {
            int v = e->v, w = e->w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
            }
        }
    }
}

外层循环 次，内层扫描 ，松弛总 ，故时间 ；稠密图 时即为 。

运行结果

Shortest distances from node 1:
  to 1: 0
  to 2: 2
  to 3: 3

优先队列实现（C++）

邻接表

vector<pair<int, int>> G[maxn];  // (终点, 边权)

核心代码

用 priority_queue 配合 greater<> 实现小根堆，堆中存 (距离, 顶点)。同一顶点可能被多次入堆；弹出时若 d > dis[u] 说明是 过期记录，直接跳过（惰性删除）：

void dijkstra(int s, int n) {
    fill(dis + 1, dis + n + 1, inf);
    dis[s] = 0;
 
    // 小根堆，存 (当前距离, 顶点)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, s);
 
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dis[u]) continue;  // 过期记录：已有更短路径到达 u
 
        // 绕道 u 尝试缩短到各邻居的距离
        for (auto [v, w] : G[u]) {
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.emplace(dis[v], v);  // 入堆；同一顶点的旧记录靠上一行跳过
            }
        }
    }
}

每次堆操作 ，最多 次入堆，总时间 。稀疏图上明显优于朴素版。

运行结果

Shortest distances from node 1 (priority queue):
  to 1: 0
  to 2: 2
  to 3: 3

两种实现对比

朴素选点 (C)优先队列 (C++)
选点方式每轮线性扫描 vis 外最小 dis小根堆取当前最小 dis
辅助结构vis[]priority_queue，无需 vis
过期处理每顶点只定型一次惰性删除：d > dis[u] 时跳过
时间复杂度
适用场景稠密图、 较小、无堆依赖稀疏图、、竞赛/工程常用

实际选型时：顶点数不大或图较稠密，朴素版代码更短、常数更小；边数远小于 时，堆优化版渐近更优。本仓库将朴素版保留为 C 邻接表实现，堆优化版单独放在 C++ 目录，便于直接复用 STL。

Graph View

Backlinks