CodeBrick 博客

Appearance

Dijkstra 算法 ​

为什么需要Dijkstra 算法 ​

在实际问题中，我们经常需要求从某一个顶点出发到图中其余各顶点的最短路径，例如导航中求从当前位置到目的地的最优路线。这类问题称为单源最短路径问题。

Dijkstra 算法是解决带权有向图（权值非负） 单源最短路径问题的经典算法，也是 408 考研图论章节的核心考点之一。理解 Dijkstra 算法，也是学习 Floyd 等其他最短路径算法的基础。

核心思想 ​

Dijkstra 算法采用贪心策略：每一轮从尚未确定最短路径的顶点中，选出距离源点最近的顶点，将其最短路径确定下来，然后用该顶点去松弛（更新）与它相邻的顶点的距离。

算法维护两个关键数组：

  • dist[]：记录源点到各顶点的当前最短距离估计值，初始时源点为 0，其余为 ∞
  • visited[]：标记顶点的最短路径是否已确定，初始全部为 false

核心操作——松弛（Relaxation）：

若 dist[u] + w(u,v) < dist[v]，则更新 dist[v] = dist[u] + w(u,v)

即：经过顶点 u 到达 v 的路径比当前已知路径更短时，就更新 v 的最短距离。

交互可视化 ​

通过下方的交互动画，你可以逐步观察Dijkstra 算法的执行过程：

加载可视化中...

操作详解 ​

算法思路 ​

  1. 初始化：dist[src] = 0，其余 dist[i] = ∞；visited[] 全部置 false
  2. 重复以下步骤 V 次（V 为顶点数）：
    • 从未访问的顶点中选出 dist 值最小的顶点 u，标记 visited[u] = true
    • 对 u 的所有邻接顶点 v 执行松弛操作：若 dist[u] + w(u,v) < dist[v]，则更新 dist[v]
  3. 算法结束后，dist[] 中即为源点到各顶点的最短路径长度

C/C++ 实现（邻接矩阵版）：

cpp
#define INF 0x3f3f3f3f
#define MAX_V 100

int graph[MAX_V][MAX_V]; // 邻接矩阵，graph[i][j] 表示边权
int dist[MAX_V];         // 源点到各顶点的最短距离
bool visited[MAX_V];     // 是否已确定最短路径

void dijkstra(int n, int src) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[src] = 0;

    for (int i = 0; i < n; i++) {
        // 选出未访问顶点中 dist 最小的顶点 u
        int u = -1, minDist = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) break; // 剩余顶点不可达
        visited[u] = true;

        // 用 u 松弛其邻接顶点
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

执行过程详解 ​

以下图为例，求从顶点 0 出发到其余各顶点的最短路径：

        1
    0 ----→ 1
    |       / \
  4 |     2/   \6
    ↓   ↙      ↓
    2 ----→ 3
        3

逐步执行过程：

轮次选中顶点 udist[0]dist[1]dist[2]dist[3]说明
初始—0∞∞∞源点距离为 0
10014∞松弛 0→1(1), 0→2(4)
210137松弛 1→2(1+2=3), 1→3(1+6=7)
320136松弛 2→3(3+3=6)
430136全部确定

加粗表示该顶点最短路径已确定（visited = true）。

负权边的局限性 ​

Dijkstra 算法不能处理含负权边的图。原因在于贪心策略的前提假设：一旦某顶点被标记为已访问，其 dist 值就是最终最短距离。但在存在负权边时，后续可能通过负权边找到更短的路径，违反了这一假设。

反例：  0 --5-→ 1 --(-3)-→ 2
        0 --3-→ 2
Dijkstra 先确定 dist[2] = 3，但实际 0→1→2 = 5+(-3) = 2 更短。

对于含负权边（无负权回路）的图，应使用 Bellman-Ford 算法。

复杂度分析 ​

实现方式时间复杂度适用场景
邻接矩阵 + 简单遍历O(V²)稠密图
邻接表 + 最小堆（优先队列）O(E log V)稀疏图

选择依据：当 E 远小于 V² 时（稀疏图），使用堆优化更高效；当 E 接近 V²（稠密图），朴素实现反而更优。

复杂度分析 ​

指标朴素实现堆优化实现
时间复杂度O(V²)O(E log V)
空间复杂度O(V²)（邻接矩阵）O(V + E)（邻接表 + 堆）

与 Floyd 算法对比：

对比项DijkstraFloyd
问题类型单源最短路径多源（所有顶点对）最短路径
时间复杂度O(V²) / O(E log V)O(V³)
负权边不支持支持（不能有负权回路）
算法思想贪心动态规划
适用场景求某一点到其余各点的最短路径求任意两点间的最短路径

考研高频考点 ​

  • ⭐ 手动模拟 Dijkstra 执行过程，填写 dist[] 表格（选择题/填空题高频）
  • ⭐ Dijkstra 不能处理负权边的原因（简答题/判断题必考）
  • ⭐ 时间复杂度 O(V²) 与堆优化 O(E log V) 的区别与适用场景
  • ⭐ Dijkstra vs Floyd 的对比（简答题高频）
  • 贪心策略的正确性理解（为什么每次选最小的 dist 是安全的）
  • 松弛操作的含义与实现

相关文章

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...