介绍

Dijkstra算法解决的是带权重的有向图上单源最短路径问题,该算法要求所有边的权重都为非负值。

算法主要通过维护结点集合S。通过从结点集V-S中选择最短路径最小的结点u,将其加入进S中,并对所有从u发出可到达V-S集合中结点的边进行松弛操作。

对邻接表进行操作

松弛操作:对于一条从 顶点u指向 顶点v的边 u–>v来说,如果满足 d[u]+w(u,v)<d[v],就更新 d[v],使得 d[v]=d[u]+w(u,v);这就是对 边uv的一次松弛操作;

其中,w(u,v)表示边的权重,d(u)表示顶点u到达源s的最短距离(目前已知)

因此我们可以将算法理解为三个操作:

  1. 找到V-S集合中距离S集合最小结点
  2. 将结点加入S集合中
  3. 对V-S中剩余结点进行松弛操作。

算法描述

解释

算法的主要逻辑为while循环。Q始终为Q=V-S。每一次通过EXTRACT-MIN(Q)取出Q中距离最小值u。并将u放入S集合中。之后在for循环中对Q中剩余结点进行松弛操作。
对距离进行更新。

分析

算法通过每次从Q中找出距离最小的一个结点插入到S中,并将Q中剩余的结点距离进行松弛,直到Q中没有结点结束。因为Q中初始结点一共有V个,因此一定会有一次O(V)操作(全部插入)。

注意到我们每次只需要松弛刚插入结点连接到的表,由于采用邻接表操作,我们对每一个边只会松弛一次,因此一共会执行|E|次。

找到最小结点的操作可以有多种方式实现,下面介绍三种。

利用一次遍历实现(常通过维护数组)

我们每一次都通过遍历Q中全部结点找到最小值,这时候需要对一次插入结点都需要执行一个O(V)操作。算法的时间复杂度为

$$ O(V^2 + E) = O(V^2) $$

利用二叉堆实现

显然,如果我们每一次都要找到最小值,可以通过使用二叉堆实现优先队列来优化寻找最小值的算法。这样我们可以将查找最小值的操作优化到O(lgV)

而对于二叉堆,每一次修改距离并加入到二叉堆都需要一次更新,因此复杂了松弛操作,时间复杂度为

$$ O((V+E)lgV) $$

即每一次删除Q中一个结点和将结点距离松弛化都需要lgV时间

因此,是否优于第一种需要考虑E的范围,即图是稀疏图还是稠密图

利用斐波那契堆

斐波那契堆的对于找到最小值并进行删除需要的时间与二叉堆一样,都是O(lgV),但对松弛操作,斐波那契堆的摊还代价是O(1),因此可以实现更好的优化,他的时间复杂度为
$$ O(VlgV + E) $$