【算法】Dijkstra 算法：解决单源最短路径问题

Dijkstra 算法

Dijkstra算法，中文名音译作迪杰斯特拉算法或戴克斯特拉算法，它是一个用来解决赋权图的单源最短路径问题的算法。

之所以这个算法名这么不好读也不好记，是因为 Dijkstra 是一个荷兰语的姓氏，很显然是它的发明者的姓氏。

荷兰科学家Edsger Wybe Dijkstra（艾兹赫尔·戴克斯特拉）在1956年发现了该算法。

赋权图

什么叫赋权图呢？就是每一条边都有一个权值的有向图或无向图。赋权图的权值可大可小，可正可负。

不过 Dijkstra 算法只处理那些所有边的权值都为非负的赋权图。严格讲，Dijkstra 算法解决的是权值非负的赋权图中的单源最短路径问题。

赋权图可以是有向的也可以是无向的，对此Dijkstra算法并不挑剔，都能处理。

单源最短路径问题

什么叫单源最短路径问题？

一般提到最短路径，我们会直接想到图中的某两个顶点之间的最短路径。Dijkstra 算法的原始版本也确实是用来找到两个顶点之间的最短路径的。

但是后来该算法进行了扩充和更新，可以在图中先选定一个顶点作为源点，然后找到图中所顶点到源点分别的最短路径——这就是单源最短路径。

算法的输入、输出与辅助存储

Dijkstra 算法的输入包括两个部分：

1）一个权值非负的赋权图；

2）图中的一个被定义为源点的顶点。

假设输入的赋权图共有 n 个顶点，则算法的输出总共包括 n 项，分别是每个顶点的名称和它们到源点的最短路径长度。

在计算源点到各顶点的最短路径时，Dijkstra 算法引入了两个集合，S 集合 (set) 与 U 集合（set）。

这两个集合中元素的数据结构相同，每个元素都包含至少两个字段：顶点名（name）和顶点到源点的最短路径长度（shortest_distance）。

S 用来盛放所有已经确定了到源点最短路径的顶点和对应最短路径长度，而 U 则被用来盛放所有其他顶点。

算法流程

Dijkstra 算法的过程非常简单直接，总体分为两大部分：i）初始化；ii）迭代更新数据。

I）初始化

在算法开始时，S 集合中总共只有一个元素，也就是源点自己，源点到源点的距离为0。

U 集合中是除了源点之外的所有节点，如果一个节点与源点直接相连，它到源点的最短距离（shortest_distance）暂时记作这个直接相连的边的权重（注意只是暂时，之后也许会调整）。而如果它和源点没有直接连通，则将其 shortest_distance 设为无穷大。

比如上面这幅图，我们取 A 作为源点。那么 Dijkstra 算法起始时，S 和 U 的内容如下：

S = [A(0)]

U = [B(3),C(6),D(5),E(∞), F(15)]

II) 迭代更新数据

迭代的结束条件是所有顶点都进入 S，而 U 为空。每一次迭代的过程如下——

第一步：对 U 内的所有元素以 shortest_distance 为依据进行升序排序：

U = [B(3),C(6),D(5),E(∞), F(15)] 调整为 U = [B(3), D(5),C(6), F(15), E(∞)]

第二步：将排序后 U 中的第一个元素（shortest_distance 最小的一个元素）移动到 S 中：

S = [A(0), B(3)]

U = [D(5),C(6),F(15), E(∞)]

第三步：重新调整 U 中现存的元素。

具体调整方法为：

i) 将 U 中的每一个元素与最新进入 S 的元素进行匹配。

如果 U 中某一个元素与 S 中最新元素相邻，且它们之间的边的权重加上 S 中那个元素的 shortest_distance 的和小于 U 中元素当前的 shortest_distance, 则 U 中的这个元素的shortest_distance 被改写，否则原值不变。

因为 7 + 3 = 10 < ∞ 因此更新 E，将其 shortest_distance 改写为 10 ：

U = [D(5),C(6),F(15), E(∞)] 调整为 U = [D(5),C(6),F(15), E(10)]

所有U中的元素都经过调整后，本步结束，进入下一轮迭代。

每一次迭代都有一个顶点进入 S，之后所有未进入 S 的顶点则根据与新进入 S 的顶点的关系调整自己与源点的已知最短距离。

如此这般重复第一到第三步，直到所有元素进入 S。

下面是 Dijkstra 算法的流程图：

对各元素 shortest_distance 的反复调整确保了最后计算出的一定是全局最优解，而非局部最优解。这是 Dijkstra 算法的一大特色！

算法的编程实现

现在来编程实现 Dijkstra 算法。

和之前一样，让我们选用邻接矩阵来描述赋权图。不过不再是简单的相邻为1，不相邻为0，而是每一个cell的值都表示两个顶点之间边的权重，如果两者不相邻，则设其值为 -1。

我们用一个类，Vertex来存储每个顶点的名称、索引和到源点的最短路径长度。

在解析邻接矩阵的时候我们做个处理，将 -1 转变为 sys.maxsize，并同步初始化S set 和 U set.

然后进入迭代：

通过迭代代码我们不难看出，这是一个两层循环嵌套的算法。

因此，可推测使用邻接矩阵作为数据结构的 Dijkstra 算法的时间复杂度为 O(n^2), n 是图中顶点的个数。

使用二叉堆或斐波那契堆作为数据结构的 Dijkstra 算法能够获得更低的时间复杂度，如果有兴趣，大家可以继续深入学习。