发新帖我要提问
返回列表
打印

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

[复制链接]
274|17
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
keer_zu|  楼主 | 2023-5-24 11:03 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式
ST, dijkstra

先上个图

使用特权

评论回复 赏

相关下载

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

使用特权

评论回复 赏
板凳
keer_zu|  楼主 | 2023-5-24 11:17 | 只看该作者


使用特权

评论回复 赏
地板
keer_zu|  楼主 | 2023-5-24 11:18 | 只看该作者

使用特权

评论回复 赏
5楼
keer_zu|  楼主 | 2023-5-24 11:19 | 只看该作者
https://zhuanlan.zhihu.com/p/129373740

使用特权

评论回复 赏
6楼
keer_zu|  楼主 | 2023-5-24 13:15 | 只看该作者
现在选择v1为原点s:


选择v_1作为原点s。

使用特权

评论回复 赏
7楼
keer_zu|  楼主 | 2023-5-24 13:16 | 只看该作者


使用特权

评论回复 赏
8楼
keer_zu|  楼主 | 2023-5-24 13:17 | 只看该作者

使用特权

评论回复 赏
9楼
keer_zu|  楼主 | 2023-5-24 13:20 | 只看该作者
以上是我们通过观察和计算比对出来的最短路径，下面我们就来看看Dijkstra 算法是如何帮助我们找到这些所有的最短路径的。
在开始之前，有几个概念需要明确一下。

使用特权

评论回复 赏
10楼
keer_zu|  楼主 | 2023-5-24 13:22 | 只看该作者
然后是Dijkstra 算法的伪码：

使用特权

评论回复 赏
11楼
keer_zu|  楼主 | 2023-5-24 13:24 | 只看该作者
下面我们来解释一下这个伪码：


使用特权

评论回复 赏
12楼
keer_zu|  楼主 | 2023-5-24 13:24 | 只看该作者

使用特权

评论回复 赏
13楼
keer_zu|  楼主 | 2023-5-24 13:27 | 只看该作者




使用特权

评论回复 赏
14楼
keer_zu|  楼主 | 2023-5-24 13:28 | 只看该作者


使用特权

评论回复 赏
15楼
keer_zu|  楼主 | 2023-5-24 13:29 | 只看该作者


使用特权

评论回复 赏
16楼
keer_zu|  楼主 | 2023-5-24 13:29 | 只看该作者


使用特权

评论回复 赏
17楼
keer_zu|  楼主 | 2023-5-24 13:30 | 只看该作者


使用特权

评论回复 赏
18楼
keer_zu|  楼主 | 2023-5-24 13:31 | 只看该作者


使用特权

评论回复 赏
返回列表
发新帖 我要提问
高级模式
B Color Image Link Quote Code 收费 Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

keer_zu
个人签名：qq群：49734243 Email:zukeqiang@gmail.com

1350

主题

12427

帖子

53

粉丝