有两种类型的成本，如何在有向无环图中找到最短路径

Question

给定一个有向无环图 G = (V,E)，可以假设已经进行了拓扑排序（如果需要）。G 中的边具有两种类型的成本 - 常规成本 w(e) 和尖峰成本 p(e)。

目标是找到从节点 s 到节点 t 的最短路径，其中最小化以下成本： sum_e (w(e)) + max_e (p(e))，其中 sum 和 maximum 是在路径上的所有边上进行的。

标准动态规划方法表明，这个问题可以在 O(E^2) 时间内解决。是否有更有效的方法来解决它？理想情况下，一个 O(E*polylog(E,V)) 算法会很好。

---- 编辑 -----

这是我使用动态规划找到的 O(E^2) 解决方案。

首先，按升序排列所有成本 p(e)。这需要 O(Elog(E)) 时间。

其次，定义由状态(x,i)组成的状态空间，其中 x 是图中的一个节点，i 在 1,2,...,|E| 中。它表示“我们在节点 x 上，并且我们已经看到的最高边权重为第 i 大”。

设 V(x,i) 是从 s 到 x 的最短路径长度（在经典意义下），其中遇到的最高 p(e) 是第 i 大。很容易计算出 V(x,i)，给定任何前驱 y 的 V(y,j)，其中 j 在 1,...,|E| 中（有两种情况要考虑 - 边 y->x 具有第 j 大的权重，或者它没有）。

在每个状态 (x,i) 处，此计算找到约 deg(x) 个值的最小值。因此，复杂度为 O(|E| * sum_(x\in V) deg(x)) = O(|E|^2)，因为每个节点与 |E| 不同的状态相关联。

- ThatGuy

---

我不确定标准DP方法在这里如何工作，因为我不清楚这个问题是否具有最优子结构。你能否详细说明一下？ - amit

是的 - 首先，您按升序排序成本p(e)。现在，您考虑状态空间，其中状态为(x,i)，其中x是图中的节点，i是1到|E|之间的数字。它表示“我们在节点x中，并且我们已经看到的最高边权重p(e)是第i大的”。相应的动态规划函数V(x,i)表示从节点s到节点t的最短路径，其中最大的p(e)成本是第i高的。您按预期进行推进，并且从V(t,i)很容易计算解决问题的路径。 - ThatGuy

此外，这是问题的重要部分，请将您的解决方案添加到问题本身中，因为它属于那里。 - amit

阅读了上面的问题和所有评论后，我仍然有疑问：这里的目的是什么？是找到所有具有最小成本的路径中分支数量最少的路径吗？ - CiaPan

你需要一个精确的答案吗？根据递减最短路径文献，找到一个高效的近似方案可能更容易。 - David Eisenstat

Answer 1

我看不到任何达到您所需的复杂度的方法。以下是一个我认为在实际中可行的算法。

首先，将图形缩小为仅包括s和t之间的顶点和边，并进行拓扑排序，以便可以轻松地在O(E)时间内找到最短路径。

让W(m)成为max(p(e)) <= m路径的最小sum(w(e))成本，让P(m)成为这些最短路径中最小的max(p(e))。问题解决方案对应于W(m)+P(m)的某个成本m。请注意，我们可以通过找到最短的W成本路径（使用P成本来打破平局）同时在O(E)时间内找到W(m)和P(m)。

m的相关值是实际发生的p(e)成本，因此请制作这些成本的排序列表。然后使用Kruskal的算法变体来查找连接s和t的最小m，并计算P(infinity)以找到最大的相关m。

现在我们有了可能是最佳的m值的区间[l,h]。该区间中可能的最佳结果为W(h)+P(l)。制作一个按最佳结果排序的间隔优先级队列，并重复删除具有最佳结果的间隔，并执行以下操作：

- 如果最佳结果=W(l)+P(l)或W(h)+P(h)，则停止。 - 如果在l和P(h)之间没有p(e)成本，则停止。 - 如果最佳结果与实际结果的差在某个可接受的公差范围内，则停止；或 - 如果您已超出一些计算预算，则停止。 - 否则，请选择在l和P(h)之间的p(e)成本t，找到最短路径以获取W(t)和P(t)，将区间拆分为[l,t]和[t,h]，并将它们放回优先级队列并重复。

获得精确结果的最坏情况复杂度仍为O(E ²)，但是有许多经济和灵活的停止方式。

- Matt Timmermans

---

请注意，这基本上是扩展了 @DavidEisenstat 的低误差容限。 - Matt Timmermans

Answer 2

这只是一个2近似算法，而不是近似方案，但也许它会激发某人想出更好的答案。

使用二分查找，找到最小的尖峰成本θ*，使得C(θ)为使用尖峰成本≤ θ的边的s-t路径的最小名义成本，我们有C(θ*) = θ*。每个解决方案的名义或尖峰成本至少与θ*一样大，因此θ*导致了一个2近似解。

二分搜索中的每个测试都涉及在尖峰成本≤ θ的子集上运行Dijkstra，因此该算法的时间复杂度为O（|E| log² |E|），如果您想技术性地使用Fibonacci堆，则为O（（|E| + |V| log |V|）log |E|）。

- David Eisenstat

---

这个图是一个有向无环图，所以你不必使用Dijkstra算法...也许有一个DAG会建议一个更好的算法，因为你熟悉这方面的文献。 - Matt Timmermans

@MattTimmermans 很遗憾，所有可能足够快的文献都是针对无向图的。 - David Eisenstat