一份让 zxj 同学都能看懂的从零开始的 dijkstra 教程。

一份让 zxj 同学都能看懂的从零开始的 dijkstra 教程。

1、普通 dijkstra

这个 zxj 同学也会,挂个链接好了。

https://www.cnblogs.com/szmssf/p/10980237.html

2、堆优化 dijkstra

2.1 回顾 dijkstra

这个 zxj 同学不会了,我来帮助他一下。

应 zxj 同学要求我先帮他说一下大概思路:

所谓堆优化 dijkstra,就是用堆优化一个 dijkstra

让我们先回顾一下 dijkstra 的形式化过程。

(1)将源点距离初始化为 \(0\) ,其它点为正无穷 \(+\infty\)

(2)经过 \(n\) 次如下操作,得到源点离其它点的最短距离:

1、选择一个未扩展的点 \(k\) ,满足 \(distance(k)\) 是未扩展节点中离源点距离最小的;

2、对 \(k\) 进行永久标号

3、以 \(k\) 为中间点修改源点到其它点的最短路距离

2.2 堆

堆是一种优秀的数据结构,有了堆可以在 \(O(\log n)\) 的时间复杂度内完成插入和弹出最大值,查询最大值。

堆是一颗完全二叉树满足父节点权值比子节点大。常见的实现方法有优先队列和左偏树,二项堆。

2.3 如何用堆这种数据结构优化 dijkstra

注意到 “选择一个未扩展的点 \(k\) ,满足 \(distance(k)\) 是未扩展节点中离源点距离最小的”

直接用堆维护所有未扩展结点,以 \(distance\) 值排序即可。

鉴于 zxj 同学并不理解 “维护” 的含义,那么通俗地来讲一讲:

每当你看到了一个新的未扩展结点,我们就把他插入堆中,以距离为第一关键字排序,这个可以参考 \(pair\) 的相关语法。

上一篇:算法模板


下一篇:最短路径算法