图(2)：最短路径算法(BFS与Dijkstra)

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为两种最短路径算法——广度优先搜索（BFS）和 Dijkstra 算法，以及 Fibonacci 堆在 Dijkstra 算法优化中的应用。

基本概念

1. ​路径定义

   • 有向图中从顶点u到v的路径是边序列，​路径长度为边数（无权图）或边权之和（有权图）。
   • ​最短路径：所有可能路径中长度最小的路径。

2. ​顶点间距离

   • $d(u, v)$：从u到v的最短路径长度。

3. ​单源最短路径问题

   • ​输入：以邻接表表示的有向图$G(V,E)$、源点$s$。
   • ​输出：$d(s, v)$，即s到各个顶点的最短距离。

BFS算法

算法思想

• ​分层扩展：从源点$s$出发，逐层向外探索顶点。
  • $V_k$：距离$s$为$k$的顶点集合。
  • 由$V_k$中顶点的邻接点构造出$V_{k+1}$。
  • 从$V_0, V_1, V_2, \ldots$开始逐层访问。

算法设计及分析

• 时间复杂度：​$O(|V| + |E|)$。
• 路径重建：记录前驱数组pre[]，可以从终点$v$回溯到$s$，逆序得到最短路径。

Dijkstra算法

适用条件

• ​带权有向图，边权非负。

算法思想

• ​贪心策略：
  • 每次选择当前距离最小的顶点，确定其最短路径。
  • ​维护最短路径树 (SPT)，逐步扩展顶点集合。

算法设计及分析

正确性证明

• 考虑将$v$加入一棵小SPT，构建更大的SPT。
• 每次选择顶点$v$为$dist_T(v)$最小者，要证$dist_T(v) = dist(v)$。
• 反证法：若存在更短路径$s \to \ldots x \to v$ ($x \notin T$)，那么有$dist_T(x) < dist_T(v)$，矛盾。

时间复杂度

• 共$|V|$轮FindMin，$|E|$轮Update。
• ​数组​：$O(|V|^2 + |E|)$。
• ​二叉堆：$O((|V| + |E|)\log |V|)$。
• ​斐波那契堆：$\bm{O(|E| + |V|\log |V|)}$。

斐波那契堆

结构概述

• ​多棵最小堆树：允许存在多棵以根节点为顶的最小堆树
• ​根链表：所有根节点通过双向循环链表连接
• ​最小指针：始终指向当前键值最小的根节点

操作步骤

​PopMin

​移除最小根节点 $\to$ 合并度数相同的树 $\to$ 更新最小指针

​Update

键值减少 ($\to$ 节点剪切到根链表 $\to$ 级联剪切)

核心结论

• 根度数为 $k$ 的树至少包含 $\sum_{i=1}^{k} fib[i] = O(C^k)$ 个节点
• 最大度数 $D$ 和根节点数 $t$ 均不超过 $O(\log n)$

均摊时间复杂度分析（势能法）

势能函数定义

$$\Phi = t + 2m$$

• $t$：当前根节点数量
• $m$：当前被标记的非根节点数量

关键操作分析

1. Update:

   • 实际时间：$C = O(\#CC + 1)$，$\#CC$ 为级联剪切次数
   • $\Delta t = \#CC + 1$，$\Delta m = -\#CC + 1$
   • $\hat{C} = C + \delta \cdot \Delta \Phi = O(\#CC + 1) + \delta \cdot (−\#CC + 3) = \bm{O(1)}$

2. PopMin:

   • 实际时间：$C = O(t^- + D)$
   • $\Delta t \le D - (t^- + D) = -t^-$
   • $\hat{C} = C + \delta \cdot \Delta \Phi \le O(t^- + D) - \delta \cdot t^- = O(D) = \bm{O(\log n)}$

注：本文中所有图片均来自张宇昊老师的课程PPT。