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

2024-03-11 22:15:13

1、普通 dijkstra

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

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

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

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

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

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

（2）经过 \(n\) 次如下操作，得到源点离其它点的最短距离：

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

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

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

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

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

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

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

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

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