求两点之间的第k短路径 陈皓.

Presentation on theme: "求两点之间的第k短路径 陈皓."— Presentation transcript:

1 求两点之间的第k短路径 陈皓

2 应用 长度之外额外的限制 模型估价 敏感性分析 ……

3 传统方法 启发式搜索（A*） 空间消耗太大！！！ 速度太慢！！！

4 新的算法 路径如何表示？ 旧的路径 + 一条不在最短路树中的新边，以及一些 关于最短路树边相关的调整信息 K小生成树的表示方法
上一棵生成树 + 修改信息（插一条边，删一条边） 旧的路径 + 一条不在最短路树中的新边，以及一些 关于最短路树边相关的调整信息

5 最短路树 最短路树T是图G的子集，是一棵根在单终点t的树， 树上点到根的路径是原图中的一条最短路 例如，上右图是上左图的最短路树

6 新的算法 对于每一条边e，定义选择e的代价 𝛿 𝑒 =𝑙 𝑒 +𝑑 ℎ𝑒𝑎𝑑 𝑒 , 𝑡 −𝑑 𝑡𝑎𝑖𝑙 𝑒 , 𝑡
其中l表示边权，d(head(e), t)是边的头到终点t的距离， d(tail(e), t)是边尾到终点t的距离 不难看出，这就是选择这一条边会增加的距离，路 径p的长度就是最短路长度加上所有边代价的和

7 新的算法 例子

8 新的算法 定义集合sidetracks(p)表示路径p上所有不在最短路树 上的边集 这样，路径p与sidetracks(p)是等价的
用lastsidestrack(p)表示最后一次加入的边，下一条边 只在边尾在T上这条边的头与t之间的路径上的边里 面选

9 堆？ 因为𝛿 𝑒 ≥0，这种表示方法有堆的性质 可惜的是，堆的叉数并没有限制，所以还需改进

10 新的算法 目标：对于每一个顶点v，构建堆 𝐻 𝐺 𝑣 ，将所有的 尾在v到t的路径上的边按𝛿(𝑒)排列
𝐻 out 𝑣 ，尾在v点的边按𝛿(𝑒)排列，最小边记为 outroot(v)，限制根只有一个孩子 𝐻 𝑇 𝑣 ，将v到t的路径上的点w的outroot按𝛿(𝑒)排列

11 新的算法 堆 𝐻 𝐺 𝑣 的构建方法：将 𝐻 𝑇 (𝑣)中的每个outroot(w) 加上一个新的儿子，就是 𝐻 𝑜𝑢𝑡 𝑤 中剩余的部分， 于是 𝐻 𝐺 𝑣 是一个三叉堆 与 𝐻 𝑇 (𝑣)同时构造

12 一棵最短路树的一部分与 𝐻 out

13 𝐻 𝑇

14 新的算法 构建一个新的图D(G)，以及从v∈G到h(v)∈D(G)映射， 满足以下性质： D(G)有O(m + n log n)个顶点
D(G)中的顶点对应图G-T中一条边 D(G)每点出度至多为3 D(G)中，由h(v)出发可达的点构成 𝐻 𝐺 𝑣

15 D(G)

16 新的算法 在D(G)的基础上，定义图P(G)，构造方法如下： 增加一个新点，根结点r，连一条初始边到h(s)，边权 为𝛿 ℎ(𝑠)
对于原有的D(G)中的边（u,v），把边权设为𝛿 𝑣 − 𝛿 𝑢 ，称作堆边 (注意u，v对应原图G-T的一条边) 对P(G)中结点v，v对应原图中的边（u,w），则在P(G) 中连边（v,h(w)），权值𝛿 ℎ(𝑤) ,称为叉边

17 新的算法 初始边：开始选择一条边 堆边：换成下一条可选择的边 叉边：选择一条新的边

18 新的算法 至此，我们只需对P(G)做广搜，从r开始第k短路径就是 原图的第k短路
P(G)的出度为4，是常数，每次只需用堆维护当前最小 的路径，扩展新的路径，所以找到k短路的复杂度为O(k log k)，算上求最短路以及构图的时间，总复杂度为O(m + n log n + k log k) 若要求多终点的k短路，只需把原图反转，终点为s，构 图方法与上述类似，复杂度O(m + n log n + k n log k)

19 改进时空性能 上述的算法的性能相比传统方法已经相当优秀
如果已经求出最短路，原图很稀疏，或者k很大， 那么n log n和k log k的项就成为了瓶颈 O(m + n + k)!!!

20 推荐习题 SGU 314, Shortest Paths

21 参考资料 [1] David Eppstein, Finding the k Shortest Paths, 1997
[2] 刘汝佳，黄亮，算法艺术与信息学竞赛，2003

22 The End Thanks for listening