k 短路

问题描述

给定一个有 个结点， 条边的有向图，求从 到 的所有不同路径中的第 短路径的长度。

A*算法

A*算法定义了一个对当前状态 的估价函数 ，其中 为从初始状态到达当前状态的实际代价， 为从当前状态到达目标状态的最佳路径的估计代价。每次取出 最优的状态 ，扩展其所有子状态，可以用 优先队列 来维护这个值。

在求解 短路问题时，令 为从当前结点到达终点 的最短路径长度。可以通过在反向图上对结点 跑单源最短路预处理出对每个结点的这个值。

由于设计的距离函数和估价函数，对于每个状态需要记录两个值，为当前到达的结点 和已经走过的距离 ，将这种状态记为 。

开始我们将初始状态 加入优先队列。每次我们取出估价函数 最小的一个状态，枚举该状态到达的结点 的所有出边，将对应的子状态加入优先队列。当我们访问到一个结点第 次时，对应的状态的 就是从 到该结点的第 短路。

优化：由于只需要求出从初始结点到目标结点的第 短路，所以已经取出的状态到达一个结点的次数大于 次时，可以不扩展其子状态。因为之前 次已经形成了 条合法路径，当前状态不会影响到最后的答案。

当图的形态是一个 元环的时候，该算法最坏是 的。但是这种算法可以在相同的复杂度内求出从起始点 到每个结点的前 短路。

实现

可持久化可并堆优化 k 短路算法

最短路树与任意路径

定义

在反向图上从 开始跑最短路，设在原图上结点 到 的最短路长度为 ，建出 任意 一棵以 为根的最短路树 。

所谓最短路径树，就是满足从树上的每个结点 到根节点 的简单路径都是 到 的 其中 一条最短路径。

性质

设一条从 到 的路径经过的边集为 ，去掉 中与 的交集得到 。

有如下性质：

1. 对于一条不在 上的边 ，其为从 到 的一条边，边权为 ，定义其代价 ，即为选择该边后路径长度的增加量。则路径 的长度 。

2. 将 和 中的所有边按照从 到 所经过的顺序依次排列，则对于 中相邻的两条边 ，有 与 相等或为其在 上的祖先。因为在 中 直接相连或中间都为树边。

3. 对于一个确定存在的 ，有且仅有一个 ，使得 。因为由于性质 ， 中相邻的两条边的起点和终点之间在 上只有一条路径。

问题转化

性质 告诉我们知道集合 后，如何求出 的值。

性质 告诉我们所有 一定满足的条件，所有满足这个条件的边集 都是合法的，也就告诉我们生成 的方法。

性质 告诉我们对于每个合法的 有且仅有一个边集 与之对应。

那么问题转化为：求 的值第 小的满足性质 的集合 。

过程

由于性质 ，我们可以记录按照从 到 的顺序排列的最后一条边和 的值，来表示一个边集 。

我们用一个小根堆来维护这样的边集 。

初始我们将起点为 或 在 上的祖先的所有的边中 最小的一条边加入小根堆。

每次取出堆顶的一个边集 ，有两种方法可以生成可能的新边集：

1. 替换 中的最后一条边为满足相同条件的 更大的边。

2. 在最后一条边后接上一条边，设 为 中最后一条边的终点，由性质 可得这条边需要满足其起点为 或 在 上的祖先。

将生成的新边集也加入小根堆。重复以上操作 次后求出的就是从 到 的第 短路。

对于每个结点 ，我们将以其为起点的边的 建成一个小根堆。为了方便查找一个结点 与 在 上的祖先在小根堆上的信息，我们将这些信息合并在一个编号为 的小根堆上。回顾以上生成新边集的方法，我们发现只要我们把紧接着可能的下一个边集加入小根堆，并保证这种生成方法可以覆盖所有可能的边集即可。记录最后选择的一条边在堆上对应的结点 ，有更优的方法生成新的边集：

1. 替换 中的最后一条边为 在堆上的左右儿子对应的边。

2. 在最后一条边后接上一条新的边，设 为 中最后一条边的终点，则接上编号为 的小根堆的堆顶结点对应的边。

用这种方法，每次生成新的边集只会扩展出最多三个结点，小根堆中的结点总数是 。

所以此算法的瓶颈在合并一个结点与其在 上的祖先的信息，如果使用朴素的二叉堆，时间复杂度为 ，空间复杂度为 ；如果使用可并堆，每次仍然需要复制堆中的全部结点，时间复杂度同样无法承受。

可持久化可并堆优化

在阅读本内容前，请先了解

可持久化可并堆 的相关知识。

使用可持久化可并堆优化合并一个结点与其在 上的祖先的信息，
每次将一个结点与其在 上的父亲合并，时间复杂度为 ，空间复杂度为 。这样在求出一个结点对应的堆时，无需复制结点且之后其父亲结点对应的堆仍然可以正常访问。

注意的是，如上文所言，最终询问时不需要可并堆的合并操作。
询问时使用优先队列维护可并堆的根，对于可并堆堆顶的删除，直接将其左右儿子加入优先队列中，
就只需要 而非 的空间。

实现

习题

「SDOI2010」魔法猪学院