专栏首页悦思悦读【算法】Dijkstra 算法:解决单源最短路径问题

【算法】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 算法能够获得更低的时间复杂度,如果有兴趣,大家可以继续深入学习。

本文分享自微信公众号 - 悦思悦读(yuesiyuedu),作者:YJL

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-06-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单源最短路径算法——Dijkstra算法

    7 2 1 2 3 1 2 3 3 4 10 2 5 5 0 4 4 2 2 4 2 5 8 6 4 1 6 6 0 1 5 1

    RainMark
  • Dijkstra算法--单源最短路径

    在http://blog.csdn.net/hacker_zhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中...

    指点
  • 最短路径问题:Dijkstra算法

    所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为路径长度)达到最小。

    233333
  • Dijkstra算法求单源最短路径

    在一个连通图中,从一个顶点到另一个顶点间可能存在多条路径,而每条路径的边数并不一定相同。如果是一个带权图,那么路径长度为路径上各边的权值的总和。两个顶点间路径长...

    Dabelv
  • 最短路径-Dijkstra算法

    Dijkstra算法,又称"迪杰斯特拉算法",是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层...

    仙士可
  • [图]最短路径-Dijkstra算法

    2.BFS可能会是Dijkstra算法的实质,BFS使用的是队列进行操作,而Dijkstra采用的是优先队列。

    王荣胜
  • 图算法|Dijkstra最短路径算法

    01 — 单源最短路径 首先解释什么是单源最短路径,所谓单源最短路径就是指定一个出发顶点,计算从该源点出发到其他所有顶点的最短路径。如下图所示,如果源点设为A,...

    double
  • 加权有向图----单点最短路径问题(Dijkstra算法)

    SuperHeroes
  • 单源最短路径 Dijkstra算法 Java 代码实现(贪心算法)

    若尘_
  • 最短路径问题--迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科学家狄克斯特拉于1959年提出,用来求从起始点到其他所有点...

    用户6021899
  • 最短路径Dijkstra算法的简单实现

    最近刷题一连碰到好几道关于最短路径的问题自己一开始用深搜过了之后也就没怎么 管,但是之后的好几道用深搜都超时,之后查了资料才知道这种最短路径的问题一般使用广搜的...

    萌萌哒的瓤瓤
  • 最短路径—大话Dijkstra算法和Floyd算法

    Dijkstra算法 算法描述 1)算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中...

    互联网金融打杂
  • 算法-最短路径:DAG、Dijkstra、Bellman-Ford

    DAG上一定存在拓扑排序,且若在有向图 G 中从顶点 u -> v有一条路径,则在拓扑排序中顶点 u 一定在顶点 v 之前,而因为在DAG图中没有环,所以按照D...

    WEBJ2EE
  • Dijkstra算法求图中最短路径

    在此借用上一篇文章[深度优先搜索(DFS)两点之间的可行路径](深度优先搜索(DFS)两点之间的可行路径)中的例子:

    带萝卜
  • 【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

    ps: 邻接矩阵的意思是: 用一个二数组表示个顶点间的关系,来确定各顶点间的关系,因为图为有向图,所以上图的邻接矩阵如上

    super.x
  • Bellman-Ford算法--解决负权边的单源最短路径算法

    在http://blog.csdn.net/hacker_zhidian/article/details/54915152这篇博客中,我们用Dijkstra算法...

    指点
  • 数据结构——最短路径Dijkstra算法

    在上一篇博文里,我记录了最小生成树的算法实现,而在这篇里,我们来讲讲查找最短路径的算法,Dijkstra算法。

    Originalee
  • 算法:最短路径之迪杰斯特拉(Dijkstra)算法

    对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉(Di...

    s1mba
  • 贪婪算法-单源最短路径

    温安适

扫码关注云+社区

领取腾讯云代金券