dj算法思维导图

Dijkstra 算法详解（边权非负）

Dijkstra 算法详解（边权非负）

单源最短路径经典算法 · 贪心策略 · 堆优化实现

Dijkstra 算法（边权非负）

核心原则

• 进入堆修改候选距离：发现更短路径时更新并入堆
• 弹出堆结算最短距离：堆顶元素即为当前未结算节点中距离最小者，一旦弹出即确定最短路径

前置准备

• 初始化距离数组 dist[]：
  • 源点 s 设为 0
  • 其余节点设为 ∞（通常用大整数如 INT_MAX / 2 表示）
• 小根堆（优先级队列）：存储 {当前候选距离, 节点编号}
• 辅助标记（按需）：
  • visited[]：用于普通堆实现，防止重复结算
  • where[]：用于反向索引堆，记录节点在堆中的位置（-2 表示已结算）

核心流程

步骤1：入堆修改（候选距离优化）

• 触发条件：遍历已结算节点 u 的邻边 u→v，若 dist[u] + w < dist[v]
• 普通堆实现：直接将 {新距离, v} 入堆（允许同一节点多次入堆）
• 反向索引堆实现：
  • 更新 dist[v]
  • 通过 where[v] 定位其在堆中位置
  • 执行上浮操作（heapify-up）维持堆性质

步骤2：出堆结算（确定最短距离）

• 触发条件：弹出堆顶元素（当前候选距离最小的节点 u）
• 普通堆实现：
  • 检查 visited[u]，若已为 true 则跳过（冗余项）
  • 否则标记 visited[u] = true，完成结算
• 反向索引堆实现：
  • 弹出后立即设置 where[u] = -2 表示已结算
  • 无需额外 visited 数组，无冗余操作

循环执行：重复上述两步，直到堆为空。

结果计算

• 遍历 dist[] 数组，取所有可达节点距离的最大值（常用于“网络延迟时间”类问题）
• 若存在任意节点 dist[i] == ∞ 且 i ≠ 源点 → 该节点不可达，根据题意返回 -1

两种堆实现对比

特性	普通堆（系统优先队列）	反向索引堆（手写堆）
数据结构	邻接表 + priority_queue	链式前向星 + 手写小根堆
入堆行为	允许多次入堆，产生冗余候选	同一节点仅存一份，直接更新并上浮
结算机制	依赖 visited[] 过滤重复	弹出即标记 where[u] = -2
优点	代码简洁，易于实现	效率最优，无冗余操作
缺点	堆中可能含大量无效项，略慢	代码稍复杂，需维护反向索引
适用场景	一般竞赛、工程快速开发	性能敏感、大规模图处理

算法复杂度

• 时间复杂度：
  • 普通堆：O((V + E) log V)
  • 反向索引堆：O(E log V)（常数更优）
• 空间复杂度：O(V + E)

注意事项

• 仅适用于边权非负的图（负权边需用 Bellman-Ford 或 SPFA）
• 初始化无穷大时避免溢出：const int INF = 0x3f3f3f3f;
• 多源最短路可考虑 Floyd-Warshall；单源稀疏图首选 Dijkstra