---
tags: [算法分析与设计]
abstract: Dijkstra 单源最短路径算法与优先队列实现
finished: false
上一篇: [[计算机系/算法分析与设计/算法分析5广搜和深搜|上一篇]]
返回目录: [[计算机系/算法分析与设计/算法分析|算法分析与设计学习指南]]
前置知识: [[计算机系/算法分析与设计/算法分析5广搜和深搜|前置知识]]
---
# Dijkstra 单源最短路径

## 问题与适用条件

Dijkstra 算法用于求解带权有向图或无向图中的单源最短路径问题，要求所有边权均为非负数。目标是从源点 $s$ 求出到各顶点的最短距离。

## 基本思想

1. 设置顶点集合 $S$，其中源点到集合内顶点的最短路径权值已经确定。
2. 反复从 $V-S$ 中选择最短路估计最小的顶点 $u$，将其加入 $S$。
3. 对 $u$ 的所有出边执行松弛：若经过 $u$ 可以缩短到邻接顶点的距离，则更新距离和前驱。

## 算法流程

1. 初始化：$dist[s]=0$，其余顶点距离设为无穷大，所有顶点标记为未确定。
2. 从未确定顶点中选取当前 $dist$ 最小者。
3. 扫描该顶点的邻接边并执行松弛。
4. 重复上述步骤，直到所有可达顶点的最短路径确定。

> [!proof] 正确性要点
> 由于边权非负，当前距离估计最小的未确定顶点不可能通过其他未确定顶点获得更短路径；因此将其加入 $S$ 后，距离即为最短距离。对每条出边进行松弛保持其余顶点的最短路估计不大于真实最短距离。

## 两种优先级队列实现

### 数组实现

每次选择最小距离顶点时线性扫描所有未确定顶点，适合规模较小或实现简单的场景。使用邻接表时，典型复杂度为 $O(|V|^2+|E|)$。

### 最小堆实现

使用最小堆维护候选顶点，每次提取当前距离最小的顶点；松弛成功后将新的距离加入堆。采用邻接表时，典型复杂度为 $O((|V|+|E|)\log |V|)$（允许堆中保留过期条目，并在弹出时检查）。

## 复杂度与注意事项

- 不能用于存在负权边的图；若需要处理负权边，应改用适合的算法。
- 空间复杂度主要来自图的存储、距离数组、前驱数组和优先级队列。
- 若需要恢复路径，应沿前驱指针从终点反向回溯至源点。