algorithm - 遍历所需边列表的最短路径

Question

我有一个有向图，看起来像这样:



我想从 中找到最便宜的路径开始到结束 其中橙色虚线都是路径有效所必需的。

自然最短路径是:开始 -> A -> B -> 结束 结果成本 = 5，但我们还没有满足所有必需的边缘访问。

我想找到的路径(通过通用解决方案)是 开始 -> A -> B -> C -> D -> B -> 结束 其中成本 = 7，我们已经满足了所有必需的边缘访问。

有没有人对如何要求这样的边缘遍历有任何想法？

Answer 1

令 R 为所需边的集合，且 F = |R|。令 G 为输入图，t (resp. s) 是所请求路径的起点(相应的结束点)。

预处理:一堆Dijkstra的算法运行......

第一步是创建另一个图形。该图将恰好有 F+2 个顶点:

R中的每条边一个

一个用于您要计算的路径的起点 t

一个用于您要计算的路径的终点 s

要创建此图，您必须执行以下操作:

从 G 中删除 R 中的每条边。

对于 R 中的每条边 E = (b,e):

计算从 t 到 b 的最短路径和从 e 到 s 的最短路径。如果它们存在，则在“新图”中添加将 s 连接到 E 的边，权衡相关最短路径的长度。

对于 R\{E} 中的每条边 E' = (b', e'):

计算从 e 到 b' 的最短路径。如果存在，则在新图中添加从 E 到 E' 的边，权衡该最短路径的长度。将计算出的路径作为有效载荷附加到相关边。

将计算出的路径作为负载附加到该边

构建此图的复杂度为 O((F+2)².(E+V).log(V))，其中 E(对应 V)是原始图中的边(对应顶点)数。

详尽搜索最佳可能路径

从这一点来看，我们必须在新创建的图中找到最短的哈密顿路径。不幸的是，这项任务是一个难题。我们没有比探索每一条可能的路径更好的方法。但这并不意味着我们不能巧妙地做到这一点。

我们将使用回溯执行搜索。我们可以通过维护两个集合来实现这一点:

当前探索的顶点列表:K(K代表已知)

当前未知的顶点列表:U(U代表未知)

在深入研究算法定义之前，这里是主要思想。除了探索新图中可能路径的整个空间之外，我们无能为力。在每一步，我们都必须做出决定:下一步要走哪条边？这会导致一系列决策，直到我们无法再移动或到达 s。但是现在我们需要回过头来取消决定，看看我们是否可以通过改变方向做得更好。要取消决定，我们可以这样进行:

每次我们卡住(或找到路径)时，我们都会取消我们做出的最后决定

每次我们在某个时刻做出决定时，我们都会跟踪哪个决定，所以当我们回到这一点时，我们知道不要做出同样的决定并探索其他可用的决定。

我们可能会卡住，因为:

我们找到了一条路。

我们无法进一步移动(没有我们可以探索的边缘，或者我们唯一可以采取的边缘会增加当前的部分路径太多——它的长度变得高于当前找到的最佳路径的长度)。

最终的算法可以用这种方式总结:(我给出了一个迭代实现，人们可以找到一个更容易和更清晰的递归实现)

让 K ← [] , L[0..R+1] ← []和 U ← V(其中 V 是工作图中每个顶点的集合减去开始和结束顶点 t 和 s)。最后让 l ← i ← 0 和 best_path_length ← ∞ 和 best_path ← []
虽然( i ≥ 0):

虽然 U ≠ []

c ← U.popFront() (我们拿U头)

L[i].pushBack(c)

如 i == R+1 AND ( l == 重量( cur_path.back() , s) + l ) < best_path_length :

best_path_length ← l

最佳路径← cur_path

如果K.tail()之间有边e和 c , 和 weight(e) + l < best_path_length :(如果K为空，则将K.tail()替换为上一条语句中的t)

K.pushBack(c)

i ← i +1

l ← weight(e) + l

cur_path.pushBack(c)

连接 L[i]末U

L[i] ← []

i ← i -1

cur_path.popBack()

在 while 循环( while (i ≥ 0) )结束时， best_path将保持最佳路径(在新图中)。从那里你只需要获取边的有效载荷来重建原始图中的路径。