有序DAG的在线最短路径
-
29-09-2020 - |
题
假设我有一个边缘加权连接的rooted dag $ g=(v,e,r \ in v,w \ in e \ to \ mathbb {z}中的m $ 存在一系列非空集(称为“级别”) $ l_0={r \},l_1 \ subset v,\ ldots,l_n \ subset v $ 使得 $ l_0 \ cup \ ldots \ cup l_n= v $ 以及 $中节点的传出边缘l_i $ 只连接到 $ l_ {i + 1} $ 。
是否有一个在线算法,可以在此表达中添加更多级别的最短路径?换句话说,它可以回答查询“从根到某些节点的最小权重路径 $ n $ 在图形的底部?”,甚至随着更多级别的添加。
我找不到解决这个问题的任何研究。
解决方案
如果我理解你的问题,那么你可能没有找到任何研究,因为问题很容易解决。
除非我错过了一些东西,您希望维护一个边缘加权“分层”DAG $ G=(L_0,\ Cup \ Dots \ Cup L_K,E)$ (如您的问题所定义)并支持以下两个操作:
-
init():仅使用一层 $ l_0 $ ,单个顶点 $ r \在l_0 $ ,没有边缘。
-
查询():return $ \ min_ {v \ in l_k} d(r,v)$ 。
-
add_layer( $ l_ {k + 1},e'$ ):您被给出了一个新的SET $ l_ {k + 1} $ 顶点和一组加权边缘 $ e'\ subseteq(l_k \ times l_ {k + 1})$ 。 $ g $ 的顶点集被更新为 $ l_0 \ cup \ ldots \ cup l_k \ cup l_ {k + 1 $ 和 $ g $ 的边缘集被更新为 $ e \ cup e'$ 。
您可以通过存储以上:1)对于每个顶点 $ v \ in l_k $ ,距离 $ d [v] $ 表单 $ s $ 到 $ v $ $ g $ ,和2)最小距离 $ d ^ * $ from $ s $ 到最后一个级别的顶点。
init操作量为设置 $ d [r]= 0 $ 。要执行查询操作,只需返回 $ d ^ * $ 。
要实现add_layer( $ l_ {k + 1},e'$ ),您按如下方式进行以下操作:
- set $ d ^ * $ to $ + \ idty $ ,
- 对于每个顶点 $ v \ in l_ {k + 1} $ :
- set $ d [v]=idty $
- 对于每个边缘 $(u,v)$ 在 $ e'$ :
- 更新 $ d [v] $ 到 $ \ min \ {d [v],d [u] + w(v)\} $
- 更新 $ d ^ * $ to $ \ min \ {d ^ *,d [v] \} $
注意,这需要时间与 $ | l_ {k + 1} | + | e'| $ ,因此是渐近最佳的。另请注意,此解决方案不需要存储 $ g $ 。
其他提示
假设您具有从根到级别的最短路径的长度 $ l_i $ ,并调用此 $ s \在l_i \ to \ mathbb {z} $ 。现在假设来自 $ l_i $ 到 $ l_ {i + 1} $ 称为