[最短路径问题]—Dijkstra 算法最详解

发表于 2023-5-24 11:03

先上个图

发表于 2023-5-24 11:09

Dijkstra 算法，是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法，戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。需要注意的是绝大多数的Dijkstra 算法不能有效处理带有负权边的图。

发表于 2023-5-24 11:17

发表于 2023-5-24 11:18

发表于 2023-5-24 11:19

https://zhuanlan.zhihu.com/p/129373740

发表于 2023-5-24 13:15

现在选择v1为原点s:

选择v_1作为原点s。

发表于 2023-5-24 13:16

发表于 2023-5-24 13:17

发表于 2023-5-24 13:20

以上是我们通过观察和计算比对出来的最短路径，下面我们就来看看Dijkstra 算法是如何帮助我们找到这些所有的最短路径的。

在开始之前，有几个概念需要明确一下。

发表于 2023-5-24 13:22

然后是Dijkstra 算法的伪码：

发表于 2023-5-24 13:24

下面我们来解释一下这个伪码：

发表于 2023-5-24 13:24

发表于 2023-5-24 13:27

发表于 2023-5-24 13:28

发表于 2023-5-24 13:29

发表于 2023-5-24 13:29

发表于 2023-5-24 13:30

发表于 2023-5-24 13:31

[最短路径问题]—Dijkstra 算法最详解

相关帖子

浏览过的版块

突出贡献奖章

沉静之湖泊

七世轮回

技术奇才奖章

浏览过的版块

突出贡献奖章

沉静之湖泊

七世轮回

技术奇才奖章