算法设计与分析：Dijkstra算法（从实现到优化）

拼搏现实的明天。 2023-06-15 11:13 15阅读 0赞

### 文章目录 ###

*  前言
 *  Dijkstra算法
 *   *  Bellman Ford算法优化回顾
     *  Dijkstra算法描述
 *  Dijkstra优化
 *   *  二叉堆
     *  二项堆
     *   *  粗略分析二项堆时间复杂度
         *  详细分析二项堆时间复杂度
         *  均摊分析法
 *  总结

> 本文参考UCAS卜东波老师算法设计与分析课程撰写

# 前言 #

在前面[算法设计与分析：贪心算法（2）- 最短路问题（DP到贪心的优化）][2_- _DP]一文中，我们已经了解了如何从动态规划一步步向贪心进行优化，本质上贪心在动态规划的基础上添加了贪心选择性质，这让我们在处理最优化问题的时候，只需要考虑局部最优（**短视**）。

> 举个简单的例子，动态规划计算第n个子问题的时候，需要保证在第n-1个子问题最优，在这基础上再获得全局的最优解；而贪心则不需要，每一步我只需考虑当前最好的即可，就像排课问题中找最早下课的，或者最短路问题中，找已遍历点中相邻最近的。这都是**短视**，而这些成立的前提是，问题具有**贪心选择性质**！如何找到这个性质，其实就是我们前面几篇文章中的优化过程，还不太理解的可以点击文末**上一篇**或者**目录**查找。

本文，我们依据前面的基础，介绍`Dijkstra算法`，这个算法在本科的时候，大家应该都耳熟能详，但本科学习的时候往往直接就给了这个算法实现过程，却没有讲述其设计的由来是通过`Bellman Ford算法`一步步优化得来的，这一点其实挺重要的。

# Dijkstra算法 #

## Bellman Ford算法优化回顾 ##

在介绍Dijkstra算法之前，先回顾一下前文`Bellman Ford`优化的点，第一点是**已遍历点中OPT值最小的无需计算**，相当于去除冗余，因此我们不需要OPT这个二维数组了，用d(v)一维存储s到v的最短路径长度，d(v)代表的就是那个最小OPT值；第二点是**只考虑已遍历点的相邻点，且从中找最近点**，这个点的s的最短路径，我们前文已经证明过，是确定的，不会再变化了，也就是说用这个点来更新d数组。

## Dijkstra算法描述 ##

好的，下面我们有Dijkstra算法的伪代码：

![在这里插入图片描述][20191122105734779.png_pic_center]  
为了更直观的理解，我绘制了一个样例如下：  
![在这里插入图片描述][20191122114154393.png_pic_center]

> 其中，绿色箭头代表最短路径，PQ存储当前各个点的d(v)值，在每一轮循环中，我们要做两件事：  
> 第一：找出所有未遍历点中d(v)值最小的，加入到已遍历点中；  
> 第二：从所有已遍历点u(u是集合S中的点)出发，走一步，依据 min ⁡ ( d ( v ) , d ( u ) + d ( u , v ) ) \\min(d(v),d(u)+d(u,v)) min(d(v),d(u)\+d(u,v))更新未遍历点v的d(v)值，每一个u都会更新一次d(v)，可能不变，可能变小  
> 具体的过程，图中已经十分详细，建议还不理解的手动画一个图（不要与我相同），自己将整个伪代码流程走一遍。

# Dijkstra优化 #

上面已经详细描述了Dijkstra算法的实现原理，但有一部分没有说清楚，就是伪代码中第7行，当更新了d(v)之后，如何从中找到最小的d(v)？

> 最简单的思路就是一个for循环遍历PQ中的d(v)找出最小的，但这显示时间复杂度太高，结合外层我们需要遍历所有点，总的时间复杂度就是 O ( n 2 ) O(n^2) O(n2)，一旦node过多，整个算法就很慢了。因此，我们需要在这点上面进行优化。

我们采用**优先队列**来存储d(v)值，即上图中的PQ集合（优先级就是node对应的d(v)值,后面统一用 k e y ( v ) key(v) key(v)），每次获取最小的值就从队列中获取，更新了 k e y ( v ) key(v) key(v)又添加到队列当中。先看一下伪代码：  
![在这里插入图片描述][20191122195613295.png_pic_center]

> 这部分实际上利用了优先队列将上面的伪代码从教抽象的文字描述转换到较具体的伪代码了，仔细对比两个伪代码不难理解各个代码的意思。其中一开始的插入操作要执行n次，获取最小 k e y ( v ) key(v) key(v)在循环中要n次，更新队列中 k e y ( v ) key(v) key(v)要m次（m是边的数量）。

依据上面的分析，我们容易知道真正影响该算法时间复杂度的是队列的三个操作`Insert`,`ExtractMin`,`DecreaseKey`，如果我们构成优先队列用的是普通的无序数组或链表，那么每次`Insert`的复杂度就只有 O ( 1 ) O(1) O(1)，但`ExtractMin`就要 O ( n ) O(n) O(n)（每次都要遍历数组、链表），如果是有序数组或链表,`Insert`需要 O ( n ) O(n) O(n)（遍历查找合适插入位置），`ExtractMin`只用 O ( 1 ) O(1) O(1)，因此，选择不同的数据结构构造队列，会导致算法时间复杂度不同，下表列出了四种实现队列的不同数据结构方式：

<table> 
 <thead> 
 <tr> 
 <th>操作</th> 
 <th>线性链表（数组）</th> 
 <th>二叉堆</th> 
 <th>二项堆*</th> 
 <th>斐波那契堆*</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>Make(创建)</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>Insert(插入):n次</td> 
 <td>1</td> 
 <td> l o g n logn logn</td> 
 <td> l o g n logn logn</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>ExtractMin(摘取最小):n次</td> 
 <td>n</td> 
 <td> l o g n logn logn</td> 
 <td> l o g n logn logn</td> 
 <td> l o g n logn logn</td> 
 </tr> 
 <tr> 
 <td>DecreasrKey(减小Key值，更新):m次</td> 
 <td>1</td> 
 <td> l o g n logn logn</td> 
 <td> l o g n logn logn</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>Delete(删除)</td> 
 <td>n</td> 
 <td> l o g n logn logn</td> 
 <td> l o g n logn logn</td> 
 <td> l o g n logn logn</td> 
 </tr> 
 <tr> 
 <td>Union(合并)</td> 
 <td>1</td> 
 <td>n</td> 
 <td> l o g n logn logn</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>FindMin(找最小)</td> 
 <td>n</td> 
 <td>1</td> 
 <td> l o g n logn logn</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>Dijkstra</td> 
 <td> O ( n ∗ 1 + n ∗ n + m ∗ 1 ) = O ( n 2 ) O(n*1+n*n+m*1) = O(n^2) O(n∗1+n∗n+m∗1)=O(n2)</td> 
 <td> O ( n ∗ l o g n + n ∗ l o g n + m ∗ l o g n ) = O ( m l o g n ) O(n*logn+n*logn+m*logn)= O(mlogn) O(n∗logn+n∗logn+m∗logn)=O(mlogn)</td> 
 <td> O ( n ∗ l o g n + n ∗ l o g n + m ∗ l o g n ) = O ( m l o g n ) O(n*logn+n*logn+m*logn)= O(mlogn) O(n∗logn+n∗logn+m∗logn)=O(mlogn)</td> 
 <td> O ( n ∗ 1 + n ∗ l o g n + m ∗ 1 ) = O ( m + n l o g n ) O(n*1+n*logn+m*1)= O(m+nlogn) O(n∗1+n∗logn+m∗1)=O(m+nlogn)</td> 
 </tr> 
 </tbody> 
</table>

> 一般来说实际问题中边的数量m要大于点的数量n

关于线性链表（数组）的分析很简单，我们重点说一下后面三者

> ExtractMin包含取最小值和从队列中删除两个操作

## 二叉堆 ##

二叉堆，实际上我们这里用的是最小堆，最小堆的特性是任意一个节点的值总是小于等于其孩子节点的值，且堆必须是完全二叉树，考虑到`Dijkstra算法`关心的三个操作（表中标黄部分），我们重点看看最小堆的这三个操作耗费时间（为什么能够降低时间复杂度）

*  `Insert`:向堆中插入元素包括2个步骤，第一是插入（将元素接到链表末尾或数组末尾），第二是维护（调整元素位置形成新堆），下面是一个例子：  
    ![在这里插入图片描述][20191123131816143.png_pic_center]
    
    > 调整的过程可以发现与对比交换的次数有关，新插入的节点若比父节点大，则无需交换，若比父节点小，则交换两者位置，过程中只需与父节点比较，因为如果小于父节点，肯定小于另一个子节点，一直对比，最多对比 l o g n logn logn次，所以`Insert`的复杂度是 O ( l o g n ) O(logn) O(logn)
 *  `ExtractMin`：前面说了这里包含两个步骤：一是返回堆顶（即最小元素），二是将堆顶元素删除（加入到已遍历点集合中），直接返回堆顶的复杂度是 O ( 1 ) O(1) O(1)，重点是删除堆顶元素之后要维护堆耗费的时间，我同样画了一个例子帮助理解：  
    ![在这里插入图片描述][20191123133711278.png_pic_center]
    
    > 值得注意的一点是，如果我们直接删除堆顶元素，再从其左右子节点中挑选较小者作为父节点，最后可能导致堆不成形，如上图所示，意味着我们要重新构造一次堆，但是如果我们先交换堆顶和尾部元素，再删除，则可以保持堆。
 *  `DecreaseKey`：更新Key值，对比某一节点，如果更新了他的Key值，则同样类似插入操作，与父节点对比，时间复杂度依然是 O ( l o g n ) O(logn) O(logn)

由此我们有利用最小堆实现优先队列的时间复杂度是  
 O ( n ∗ l o g n ( n 次 i n s e r t ) + n ∗ l o g n ( n 次 E x t r a c t M i n ) + m ∗ l o g n ( m 次 D e c r e a s e K e y ) ) = O ( m l o g n ) O(n\*logn(n次insert) + n\*logn(n次ExtractMin)+m\*logn(m次DecreaseKey))\\\\= O(mlogn) O(n∗logn(n次insert)\+n∗logn(n次ExtractMin)\+m∗logn(m次DecreaseKey))=O(mlogn)

> 二叉堆的存储可以依靠链表或数组两种方式，网上有很多实现解释，在这不再赘述

## 二项堆 ##

又称二项树，它在二叉堆的基础上优化了合并堆耗费的时间（从 O ( n ) O(n) O(n)到 O ( l o g n ) O(logn) O(logn)）。  
之前的二叉堆采用单棵树的方式存储，而在二项堆中采用多棵树表示。下面是二项树的严格定义：

*  单个节点可以作为一个二项堆
 *  一个二项堆必由两个大小相同的二项树按照规则（将树根小的接在另一棵树的根节点下）

> 而二项堆由多个二项树构成（森林），为了方便，我们将只含一个节点的二项树称作 B 0 B\_0 B0，将两个 B 0 B\_0 B0组合成的二项树称作 B 1 B\_1 B1，以此类推

如下图（图片来源课件）：  
![在这里插入图片描述][20191123145626374.png_pic_center]  
如果一个堆中出现两棵级别一样的树，就将它们合并。因此一个二项堆中若容纳n棵树，实际上最多只会有 \[ l o g 2 n + 1 \] \[log\_2n+1\] \[log2n\+1\]棵树（合并过后），最高树的高度是 \[ l o g 2 n \] \[log\_2n\] \[log2n\]，我们重点考察一下二项堆的时间开销：

### 粗略分析二项堆时间复杂度 ###

*  合并(union)
    
     *  没有大小相同的树  
        直接放在一起
        
        > 如\{  B 1 , B 2 B\_1,B\_2 B1,B2\}和\{  B 3 , B 4 B\_3,B\_4 B3,B4\}变成\{  B 1 , B 2 , B 3 , B 4 B\_1,B\_2,B\_3,B\_4 B1,B2,B3,B4\}
     *  有大小相同的树  
        将大小相同的合并，直到没有大小相同为止，两个二项树变成一个耗费 O ( 1 ) O(1) O(1)，合并森林依据树的总数量不超过 O ( l o g n ) O(logn) O(logn)
        
        > 如\{  B 1 , B 2 B\_1,B\_2 B1,B2\}和\{  B 2 , B 3 B\_2,B\_3 B2,B3\} → \\to →\{  B 1 , B 3 , B 3 B\_1,B\_3,B\_3 B1,B3,B3\} → \\to →\{  B 1 , B 4 B\_1,B\_4 B1,B4\}
 *  插入(insert)  
    若原先二项堆中无 B 0 B\_0 B0，直接放入，若有，两个 B 0 B\_0 B0构成 B 1 B\_1 B1，不断合并，耗费 O ( l o g n ) O(logn) O(logn)
 *  取出最小(ExtractMin)  
    先获取最小，是从不超过 l o g n logn logn棵树中对比根节点， O ( l o g n ) O(logn) O(logn)，取走根后，一棵二项树拆成两棵二项树，可能会与其他合并，合并还是 O ( l o g n ) O(logn) O(logn)，总时间 O ( l o g n ) O(logn) O(logn)

因此，我们得出简单结论，二项堆相比二叉堆，提高了union操作的效率。

> 看到此处，你是否有一个疑问？在`Dijkstra算法`中，我们只用到了三个操作，并不涉及union，而二项堆相比于二叉堆只是优化了union的效率，对照表格中可以发现两者在`Dijkstra`上复杂度都是 O ( m l o g n ) O(mlogn) O(mlogn)。为何还有这个必要对union优化?

我个人的理解是，从树的数量上来看，二叉堆仅用了一棵树，而二项堆是一个森林，如果二叉堆在构建的时候(也就是一个个插入元素的时候，刚好是有序的，那么构建得到的二叉堆就是线性的（你可以纸上画画看），这就退化到了线性链表，而二项堆因为有多个树，相比于二叉堆，它要更为稳定，但是因为它中间涉及到二项树的合并操作，因此要在union上进行优化。

### 详细分析二项堆时间复杂度 ###

由上文我们已经粗略计算了二项堆`insert`和`union`的时间是 l o g n logn logn，事实上，我们还可以进一步确定其时间复杂度可以到达 O ( 1 ) O(1) O(1)

首先回顾一下前一篇文章中对二项堆插入操作的分析，当我们插入一个元素的时候将其视作 B 0 B\_0 B0，如果不存在 B 0 B\_0 B0，则 O ( 1 ) O(1) O(1)，如果存在，我们需要将两个 B 0 B\_0 B0合并成 B 1 B\_1 B1,再看有没有 B 1 B\_1 B1存在，以此类推。但实际上，大多数情况下我们插入一个元素都是 O ( 1 ) O(1) O(1)。看下面这个例子：

> 假设某一次插入之后，耗费O(logn)的时间，使得二项堆合并到最后就剩一个二项树了，那么下一次插入必然只耗费O(1)的时间，如下图（来源课件）所示：  
> ![在这里插入图片描述][20191123163036299.png_pic_center]

更进一步分析，假设某一次耗费 O ( l o g n ) O(logn) O(logn)，我们计算在那次之后不断插入元素的时间消耗，显然有 O ( 1 ) , O ( 2 ) , O ( 1 ) , O ( 3 ) , O ( 1 ) . . . O(1),O(2),O(1),O(3),O(1)... O(1),O(2),O(1),O(3),O(1)...我们发现，在很长一段时间内，插入耗费的时间都是常数阶的。因此，我们不能单一地根据一次时间消耗是 O ( l o g n ) O(logn) O(logn)而断言时间复杂度是 O ( l o g n ) O(logn) O(logn)，需要考虑一串操作的整体期望时间复杂度。

### 均摊分析法 ###

关于均摊分析，实际上在[算法设计与分析：分治思想（2）- 选择问题（对单个数组归约）][2_-]中，我已经粗略说明过，忘记的可以回去文章看一下。课本上给的证明过程我觉得不太好理解，因此我们直接以n个元素插入作为实例，看看整体的期望时间复杂度是多少，如下图例：  
![在这里插入图片描述][20191123173543711.png_pic_center]  
我们发现只有在编号是2的幂的时候，时间消耗会较高（即logn），其他情况下都可以看作常数时间，我们不妨按照一个区间去考虑总的期望时间消耗，按照上图的例子，将5678看作一个区间，8消耗太多，均匀分给前面的；将34看作一个区间，4消耗太多，均匀分给前面；可以发现我们使得所有编号耗费的时间都只有常数 O ( 2 ) O(2) O(2)，因此，针对插入元素区间 ( 2 m , 2 m + 1 \] (2^m,2^\{m+1\}\] (2m,2m\+1\]，我们可以将编号 2 m + 1 2^\{m+1\} 2m\+1的时间耗费均摊到整个区间的所有元素上，使得整个区间都是常数级插入时间，为什么这一点能够成立？

观察可以得知当我们在2的幂位置形成完整的二项树之后，每一个 ( 2 m − 1 , 2 m \] (2^\{m-1\},2^m\] (2m−1,2m\]区间，实际上开始重复上一区间过程，什么意思？我们将每一段区间形成消耗时间的过程都一分为二，例如5-8分为形成5-6和形成7-8两个过程（标记为 p 56 , p 78 p\_\{56\},p\_\{78\} p56,p78），3-4为形成3和形成4的过程( p 3 p\_3 p3)，前一个 p 4 p\_4 p4， p 3 p\_3 p3与 p 1 p\_1 p1对应， p 4 p\_4 p4与 p 2 p\_2 p2对应，但是为什么 p 3 = p 1 ， p 4 = p 2 + 1 p\_3=p\_1，p\_4=p\_2+1 p3=p1，p4=p2\+1？因为，在 p 4 p\_4 p4多了一步将两个 p 2 p\_2 p2合并。同理我们有 p 56 p\_\{56\} p56与 p 12 p\_\{12\} p12对应， p 78 p\_\{78\} p78与 p 34 p\_\{34\} p34对应，进一步将5和1对应，6和2对应，7和3对应，8和4对应，前面三个都是相等，到8和4时，由于 p 8 p\_8 p8要将两个 p 4 p\_4 p4合并多了一步。  
以此类推，我们有 p 916 p\_\{916\} p916与 p 18 p\_\{18\} p18对应，递归下去, p 912 p\_\{912\} p912与 p 14 p\_\{14\} p14对应， p 1316 p\_\{1316\} p1316与 p 58 p\_\{58\} p58对应，一直递归到p的下表区间长度为1，我们容易发现除了 2 m 2^m 2m的位置会多了1以外，**其余刚好全部对应相等**。  
这种对应有什么好处？好处在于我们可以将后一个区间的均摊映射到前一个区间的均摊，我们每次要均摊区间 ( 2 m , 2 m + 1 \] (2^m,2\{m+1\}\] (2m,2m\+1\]时，都可以与 \[ 1 , 2 m \] \[1,2^m\] \[1,2m\]一一对应，而前者是可以均摊的，后者与前者不一样的地方就是最后多了1，而这个1完全可以放到编号1上去。有一点数学归纳的味道。

> 我们以1-8为例，当我们考虑 \[ 5 , 8 \] 时 \[5,8\]时 \[5,8\]时将其与\[1,4\]对应，查看它们消耗分别是`1213`,`1214`，而我们知道 \[ 1 , 4 \] \[1,4\] \[1,4\]是可以均摊的，结果是`1222`,所以 \[ 5 , 8 \] \[5,8\] \[5,8\]也是可以均摊的，多出的1就放到编号5的位置,结果是`2222`。

根据上面的分析实际上我们可以得出对于 \[ 1 , 2 m \] \[1,2^m\] \[1,2m\]区间上总的操作数：  
 O P ( 1 , 2 m ) = 2 O P ( 1 , 2 m − 1 ) + 1 = 2 ( 2 O P ( 1 , 2 m − 2 + 1 ) + 1 ) = . . . = 2 m O P ( 1 , 1 ) + m = 2 m + 1 + 2 + 4... + 2 m − 1 = 2 m + 1 − 1 OP(1,2^m) = 2OP(1,2^\{m-1\}) + 1 = \\\\2(2OP(1,2^\{m-2\}+1)+1)\\\\=...\\\\=2^mOP(1,1)+m\\\\=2^m+ 1+2+4...+2^\{m-1\}\\\\=2^\{m+1\}-1 OP(1,2m)=2OP(1,2m−1)\+1=2(2OP(1,2m−2\+1)\+1)=...=2mOP(1,1)\+m=2m\+1\+2\+4...\+2m−1=2m\+1−1  
那么每个点上消耗的时间(即均摊到区间 ( 1 , 2 m \] (1,2^m\] (1,2m\]每个点上)，即时间复杂度为：  
 T ( m ) = O ( 2 m + 1 − 1 2 m ) = O ( 2 ) T(m) = O(\\frac\{2^\{m+1\}-1\}\{2^m\}) = O(2) T(m)=O(2m2m\+1−1)=O(2)

> 其中，相当于我们对 \[ 1 , 2 m \] \[1,2^m\] \[1,2m\]的时间复杂度分成两个等同区间的时间复杂度，但是后一个区间因为要多一步合并操作，因此+1。在均摊的时候之所以没有将**编号1**的位置加入均摊，是因为不需要，你会发现所有的情况均摊后的时间结果都是`122222...`的形式。

综合以上考虑，最终我们的结果是`insert`的实际期望复杂度应该是 O ( 2 ) = O ( 1 ) O(2)=O(1) O(2)=O(1)

> 这个部分开始让我挺纠结的，给你的感觉就是好像是那么回事，但是语言又不知道怎么叙述，最后想到了用这种一一对应关系的方式叙述解决，强烈建议好好理解这部分内容，而不是记一个结论就好！

关于二项堆union的操作只用 O ( 1 ) O(1) O(1)其实类似，这里不多赘述，有兴趣的自己可以推导看看

# 总结 #

本文我们介绍了Dijkstra的原理和详细设计过程，并且包含部分优化的内容，重要的一点是，有别于一般文章中直接给出`Dijkstra`，本文在前文`Bellmen Ford算法`优化基础上才引出了`Dijkstra`，这也是一个典型的DP到Greedy的思想转化。通常情况下，我们设计算法，会先从DP入手，发现其中有冗余计算且满足贪心选择性质后，再将其优化成Greedy。  
此外，本文引入了两个新的数据结构：二叉堆与二项堆，它们的设计是我们在算法设计过程中的另一种优化，从数据结构上优化算法。

*  二叉堆  
    可以快速获取队列最小值，且拥有快速的插入和删除速度
 *  二项堆  
    在二叉堆的基础上，降低了堆合并和插入操作耗费的时间

我们从一开始使用线性链表实现优先队列，发现求最小太慢，改为有序链表，发现插入太慢，可见限制条件一下子放松过多，从而我们退而求其次，采用二叉堆，放松了部分限制，使得插入和取最小的时间复杂度都在合理范围之内。

> 如果你觉得文章对你有用，不妨顺手点个赞哦～

*  上一篇：[算法设计与分析：贪心算法（2）- 最短路问题（DP到贪心的优化）][2_- _DP]
 *  下一篇：to be continue>>>
 *  [目录][Link 1]

[2_- _DP]: https://blog.csdn.net/GentleCP/article/details/103099264
[20191122105734779.png_pic_center]: https://img-blog.csdnimg.cn/20191122105734779.png#pic_center
[20191122114154393.png_pic_center]: https://img-blog.csdnimg.cn/20191122114154393.png#pic_center
[20191122195613295.png_pic_center]: https://img-blog.csdnimg.cn/20191122195613295.png#pic_center
[20191123131816143.png_pic_center]: https://img-blog.csdnimg.cn/20191123131816143.png#pic_center
[20191123133711278.png_pic_center]: https://img-blog.csdnimg.cn/20191123133711278.png#pic_center
[20191123145626374.png_pic_center]: https://img-blog.csdnimg.cn/20191123145626374.png#pic_center
[20191123163036299.png_pic_center]: https://img-blog.csdnimg.cn/20191123163036299.png#pic_center
[2_-]: https://blog.csdn.net/GentleCP/article/details/101512092
[20191123173543711.png_pic_center]: https://img-blog.csdnimg.cn/20191123173543711.png#pic_center
[Link 1]: https://blog.csdn.net/GentleCP/article/details/102609055