跳转至

Dijkstra

Dijkstra 算法的本质是求出从源点出发到每一个节点的最优路径的过程。它对松弛过程有如下要求：

  • 对节点 \(u\) 进行一次新的松弛，\(u\) 的答案不劣；
  • 在 \(u\) 比 \(v\) 不劣时，一次松弛 \((u,v)\) 不会使 \(v\) 变得比 \(u\) 更优；

对于朴素 Dijkstra，每次 \(O(n)\) 找到 \(vis=0\) 且 \(d\) 最小的一个点，进行松弛；时间复杂度 \(O(n^2)\)。

对于堆优化 Dijkstra，每次 \(O(\log m)\) 取出堆顶进行松弛；最多松弛 \(m\) 次；时间复杂度 \(O(m\log m)\)。

在 \(m\) 不超过 \(O(\frac{n^2}{\log m})\) 时，使用堆优化 Dijkstra 即可。其余情况用朴素 Dijkstra 更优。

例题

符号和约定

  • 记 \(dis(a,b),\ d(a,b)\) 表示图上 \(a\to b\) 最短路的长度；
  • 源点到 \(u\) 的距离简记为 \(d(u)\)；

CF1842D Tenzing and His Animal Friends

Tenzing 有 n 个朋友，每次举办聚会可以邀请一些朋友，有如下限制：

  • 1 必须参加，n 不能参加。

  • 有 m 条限制 (u,v,w)，表示 u 和 v 中只有一个在聚会中的总时间不超过 w。

最大化聚会总时间，并给出相应方案，即给出总聚会时间，每次聚会给出参与聚会的人和单次聚会时长。

先将问题刻画到图上，将 \((u,v,w)\) 视为图上一条边。先考虑一些特殊的情况：对于和 \(1\) 相邻的节点 \(u\)，它为 \(0\) 的时间不能超过 \(1\to u\) 的边权。再考虑和 \(u\) 相邻的节点 \(v\)，它在 \(u\) 为 \(0\) 的时候显然不受到 \(u\to v\) 边的限制可以取为 \(0\)，而在其余时间 \(s_u=1\)（\(s\) 表示方案）时，\(s_v=0\) 的时间有不能超过 \(u\to v\) 的边权；因此 \(s_v=0\) 的总时间不能超过 \(1\to v\) 的最短路，而且显然可以取到这个上界。容易归纳得到每个节点都满足这个性质。

考虑和 \(n\) 相邻的节点 \(u\)，它满足 \(s_u=0\) 的时间不超过 \(d(u)\)，其余时间都为 \(1\)。但是它为 \(1\) 的时间又不能超过 \((u,n)\) 的边权，因此答案不能超过 \(\min\{d(u)+w(u,n)\}=d(n)\)，也显然可以取等。这样我们就做完了第一问。

上面归纳证明的过程已经给出了一种构造方法，我们从小到大扫描所有 \(d(i)\)，将 \(d(u)\) 不超过当前指针（扫描线）的节点都标为 \(1\) 即可。

HLP3460 最小距离(distance)

题目描述 给定一张n个点m条边的带边权连通无向图，其中有p个点是特殊点。

对于每个特殊点，求出它到离它最近的其它特殊点的距离。

输入格式 第一行三个整数n,m,p，第二行p个整数x1~xp表示特殊点的编号。接下来m行每行三个整数u,v,w表示一条连接u和v，长度为w的边。

输出格式 输出一行p个整数，第i个整数表示xi的答案。

考虑多源最短路，两个关键点碰面的时候更新双方的答案即可。时间复杂度 \(O(m\log n)\)。

C23068 造题(maze)

给定一个无向连通图，边有边权，走到一个点时图上会存在不超过 \(d\) 条边不能走。图上有 \(k\) 个出口，问从 \(1\) 号节点走到任意一个出口的最短路是多少。

\(n\le 10^5,\ m\le 10^6,\ d\le 20\)

不难发现没有后效性（前面的选择对后面没有影响）。先考虑判断有解。从一个节点 \(u\) 出发能走到出口的充要条件是 \(u\) 存在（严格）多于 \(d\) 条出边连向另一些可行的节点（好像有循环论述的问题，不过问题不大，意会即可，此处不重要）。这启发我们写出另一种更严谨的表述：不断选择图中满足“有至少 \(d\) 条出边连向其它可行节点”的节点，将它们标记为可行。

现在考虑如何求出一个节点的答案。仍然考虑上面的过程，我们在加入一个点时，取它所有出边的第 \(d+1\) 小值（\(d[v]+w\)）作为它的答案 \(d[u]\)。考虑多源最短路 Dijkstra，随着一个节点的出边不断被考虑，它的答案不断变优；当它的答案已经不劣于当前正在松弛的节点（\(u\)）时，它的答案就是最终答案。

那么如何在加入出边的过程中动态维护答案呢？我们可以给每个节点单独开一个堆，用来维护 \(d+1\) 小值即可。若不存在，则代表该节点暂时不能到达出口。

P6742 [BalticOI 2014] Portals (Day2)

给定一个 \(n\times m\) 的迷宫，迷宫中有墙、空地、起点和终点，坐标不在 \(n\times m\) 的位置都是墙。每单位时间，你可以进行如下操作中的一种：

  • 向上下左右四个方向的非墙位置移动一格；
  • （当传送门数量恰好为 \(2\) 个）穿过面前的传送门（即，）；

在任意时刻，你可以向上下左右四个方向中的一个发射一个传送门，传送门会贴在该方向最近的墙上；你也可以删除任意传送门；但你需要保证任意时刻至多存在两个传送门。

问从起点走到终点的最短时间。

\(n,m\le 1000\)

不难得到一个传送门不会使用多于一次；并且容易发现，一对传送门一定在一个位置发射（显然不会绕墙，其余情况我们一定可以找到一个位置同时发射两个传送门）。因此，我们维护出上下左右四个方向最近的墙有多远，然后跑最短路，走到一个点时处理一下发射传送门的的情况即可。

关于结论的证明，可以参考洛谷题解。

CF1801D The way home

不难注意到每次演出的收益随时间单调不降，因此演出有一定的顺序，考虑排序后 dp。设 \(f_i\) 表示上一次演出是在节点 \(i\)。我们枚举收益比 \(i\) 小的节点 \(j\)，然后从 \(f_j\) 沿 \(j\to i\) 的最短路转移过来。时间复杂度 \(O(n^2)\)。

全源最短路可以用 Floyd \(O(n^3)\) 求出，也可以用 Dijkstra 在 \(O(nm\log n)\) 内求出。

[ABC307F] Virus 2

由于一次传播可能存在某些边没有被跨过。如果每次都跑多源最短路，时间复杂度不对，因为一条边可能被松弛多次。注意到在一次传播中，连接两个感染者之间的边一定不会造成有效的松弛。因此我们记录所有跨过感染者和未感染者的边，取其中长度小于 \(x_i\) 的边扔进最短路里面。不难发现一定不会走到以前松弛过的边。

用堆维护处于边界上的边即可。注意一条边从堆里取出来时，两端点可能都已经被感染；这种情况直接忽略即可。时间复杂度 \(O(m\log n)\)。