.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料堆的可持久化和 k 短路俞鼎力Leo.DingliYugmail.com绍兴市第一中学2014 年 2 月 8 日.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料目录k 短路定义A* 算法数据规模问题转化求解与优化堆的可持久化什么样的堆可能可以可持久化Brodal Queue二叉堆二项堆.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料Outlinek 短路定义A* 算法数据规模问题转化求解与优化堆的可持久化什么样的堆可能可以可持久化Brodal Queue二叉堆二项堆.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料定义这里，k 短路是要求在一张有向带权图 G 中，从起点 s 到终点 t 的可重复经过同一点的不严格递增的第 k 短路的长度。由于之后的算法的一些限制，我们先默认边权非负。对于一条边 e，定义它的边权（长度）为 (e)，定义它的起始点为 head(e)、终止点为 tail(e)。用 d(u,v) 表示 u 到 v 的最短距离。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料定义这里，k 短路是要求在一张有向带权图 G 中，从起点 s 到终点 t 的可重复经过同一点的不严格递增的第 k 短路的长度。由于之后的算法的一些限制，我们先默认边权非负。对于一条边 e，定义它的边权（长度）为 (e)，定义它的起始点为 head(e)、终止点为 tail(e)。用 d(u,v) 表示 u 到 v 的最短距离。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料定义这里，k 短路是要求在一张有向带权图 G 中，从起点 s 到终点 t 的可重复经过同一点的不严格递增的第 k 短路的长度。由于之后的算法的一些限制，我们先默认边权非负。对于一条边 e，定义它的边权（长度）为 (e)，定义它的起始点为 head(e)、终止点为 tail(e)。用 d(u,v) 表示 u 到 v 的最短距离。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料定义这里，k 短路是要求在一张有向带权图 G 中，从起点 s 到终点 t 的可重复经过同一点的不严格递增的第 k 短路的长度。由于之后的算法的一些限制，我们先默认边权非负。对于一条边 e，定义它的边权（长度）为 (e)，定义它的起始点为 head(e)、终止点为 tail(e)。用 d(u,v) 表示 u 到 v 的最短距离。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料Outlinek 短路定义A* 算法数据规模问题转化求解与优化堆的可持久化什么样的堆可能可以可持久化Brodal Queue二叉堆二项堆.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料A* 算法众所周知，解决 k 短路问题的经典算法是 A*，算法核心在于对当前状态的估价。使用 A* 求 k 短路的主要流程是这样的：将所有边反向并使用最短路算法，得到任意一点 v 到终点 t的最短路径 d(v,t)。一开始状态位于点 s，假设经过一段时间走到了点 v，那么定义当时的估价值为已经走过的路径长度 +d(v,t)。用一个堆 Q 来维护所有状态的估价值，每次从 Q 中取出估价最小的状态，枚举其下一步走的边，将新的状态及其估价值放入 Q 中。直到找到 k 条 s 到 t 的路径为止。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料A* 算法众所周知，解决 k 短路问题的经典算法是 A*，算法核心在于对当前状态的估价。使用 A* 求 k 短路的主要流程是这样的：将所有边反向并使用最短路算法，得到任意一点 v 到终点 t的最短路径 d(v,t)。一开始状态位于点 s，假设经过一段时间走到了点 v，那么定义当时的估价值为已经走过的路径长度 +d(v,t)。用一个堆 Q 来维护所有状态的估价值，每次从 Q 中取出估价最小的状态，枚举其下一步走的边，将新的状态及其估价值放入 Q 中。直到找到 k 条 s 到 t 的路径为止。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料A* 算法众所周知，解决 k 短路问题的经典算法是 A*，算法核心在于对当前状态的估价。使用 A* 求 k 短路的主要流程是这样的：将所有边反向并使用最短路算法，得到任意一点 v 到终点 t的最短路径 d(v,t)。一开始状态位于点 s，假设经过一段时间走到了点 v，那么定义当时的估价值为已经走过的路径长度 +d(v,t)。用一个堆 Q 来维护所有状态的估价值，每次从 Q 中取出估价最小的状态，枚举其下一步走的边，将新的状态及其估价值放入 Q 中。直到找到 k 条 s 到 t 的路径为止。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料A* 算法众所周知，解决 k 短路问题的经典算法是 A*，算法核心在于对当前状态的估价。使用 A* 求 k 短路的主要流程是这样的：将所有边反向并使用最短路算法，得到任意一点 v 到终点 t的最短路径 d(v,t)。一开始状态位于点 s，假设经过一段时间走到了点 v，那么定义当时的估价值为已经走过的路径长度 +d(v,t)。用一个堆 Q 来维护所有状态的估价值，每次从 Q 中取出估价最小的状态，枚举其下一步走的边，将新的状态及其估价值放入 Q 中。直到找到 k 条 s 到 t 的路径为止。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料A* 算法众所周知，解决 k 短路问题的经典算法是 A*，算法核心在于对当前状态的估价。使用 A* 求 k 短路的主要流程是这样的：将所有边反向并使用最短路算法，得到任意一点 v 到终点 t的最短路径 d(v,t)。一开始状态位于点 s，假设经过一段时间走到了点 v，那么定义当时的估价值为已经走过的路径长度 +d(v,t)。用一个堆 Q 来维护所有状态的估价值，每次从 Q 中取出估价最小的状态，枚举其下一步走的边，将新的状态及其估价值放入 Q 中。直到找到 k 条 s 到 t 的路径为止。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料A* 算法众所周知，解决 k 短路问题的经典算法是 A*，算法核心在于对当前状态的估价。使用 A* 求 k 短路的主要流程是这样的：将所有边反向并使用最短路算法，得到任意一点 v 到终点 t的最短路径 d(v,t)。一开始状态位于点 s，假设经过一段时间走到了点 v，那么定义当时的估价值为已经走过的路径长度 +d(v,t)。用一个堆 Q 来维护所有状态的估价值，每次从 Q 中取出估价最小的状态，枚举其下一步走的边，将新的状态及其估价值放入 Q 中。直到找到 k 条 s 到 t 的路径为止。.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料Outlinek 短路定义A* 算法数据规模问题转化求解与优化堆的可持久化什么样的堆可能可以可持久化Brodal Queue二叉堆二项堆.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料数据规模没听懂？没关系，等下讲的和这个毫无关系。你只要知道如果这张图恰好是一个 n 元环的话，A* 算法的复杂度是 O(nk) 的。有同学想知道 k = 10000 怎么做么？有同学想知道 k = 100000 怎么做么？有同学想知道 k = 1000000 怎么做么？.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料数据规模没听懂？没关系，等下讲的和这个毫无关系。你只要知道如果这张图恰好是一个 n 元环的话，A* 算法的复杂度是 O(nk) 的。有同学想知道 k = 10000 怎么做么？有同学想知道 k = 100000 怎么做么？有同学想知道 k = 1000000 怎么做么？.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料数据规模没听懂？没关系，等下讲的和这个毫无关系。你只要知道如果这张图恰好是一个 n 元环的话，A* 算法的复杂度是 O(nk) 的。有同学想知道 k = 10000 怎么做么？有同学想知道 k = 100000 怎么做么？有同学想知道 k = 1000000 怎么做么？.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料数据规模没听懂？没关系，等下讲的和这个毫无关系。你只要知道如果这张图恰好是一个 n 元环的话，A* 算法的复杂度是 O(nk) 的。有同学想知道 k = 10000 怎么做么？有同学想知道 k = 100000 怎么做么？有同学想知道 k = 1000000 怎么做么？.目录 . . . . . . . . . . . . . . . .k 短路 . . . . . . . . . . . . . . . .堆的可持久化参考资料数据规模没听懂？没关系，等下讲的和这个毫无关系。你只要知道如果这张图恰好是一个 n 元环的话，A* 算法的复杂度是 O