algorithm - 具有两种成本的有向无环图中的最短路径

Question

我得到一个有向无环图 G = (V,E)，可以假设它是拓扑有序的(如果需要)。 G 中的边有两种类型的成本 - 名义成本 w(e) 和尖峰成本 p(e)。
目标是找到从节点 s 到节点 t 的最短路径，以最小化以下成本:
sum_e (w(e)) + max_e (p(e))，其中总和和最大值取路径中的所有边。
标准的动态规划方法表明这个问题可以在 O(E^2) 时间内解决。有没有更有效的方法来解决它？理想情况下，O(E*polylog(E,V)) 算法会很好。
- - 编辑 - - -
这是我使用动态规划找到的 O(E^2) 解决方案。
首先，按升序排列所有成本 p(e)。这需要 O(Elog(E)) 时间。
其次，定义由状态 (x,i) 组成的状态空间，其中 x 是图中的一个节点，i 在 1,2,...,|E| 中。它表示“我们在节点 x 中，到目前为止我们看到的最高边权重 p(e) 是第 i 个最大的”。
设 V(x,i) 是从 s 到 x 的最短路径(在经典意义上)的长度，其中遇到的最高 p(e) 是第 i 个最大的。给定 V(y,j) 对于 x 的任何前驱 y 和 1,...,|E| 中的任何 j，计算 V(x,i) 很容易(有两种情况需要考虑 - 边 y->x 是第 j 个最大权重，或者不是)。
在每个状态 (x,i) 处，此计算会找到约 deg(x) 值中的最小值。因此，复杂度为 O(|E| * sum_(x\in V) deg(x)) = O(|E|^2)，因为每个节点都与 |E| 相关联不同的状态。

Answer 1

我看不到任何方法可以获得您想要的复杂性。这是我认为在现实生活中实用的算法。
首先，将图缩减为仅 s 和 t 之间的顶点和边，并进行拓扑排序，以便您可以在 O(E) 时间内轻松找到最短路径。
让 W(m) 是路径 max(p(e)) <= m 的最小 sum(w(e)) 成本，让 P(m) 是这些最短路径中最小的 max(p(e))。对于某些成本 m，问题解决方案对应于 W(m)+P(m)。请注意，我们可以通过找到最短的 W-cost 路径，使用 P-cost 打破平局，在 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) 之间选择 ap(e) 成本 t，找到最短路径得到 W(t) 和 P(t)，将区间拆分为 [l,t] 和 [t,h]，以及将它们放回优先队列并重复。

获得准确结果的最坏情况复杂度仍然是 O(E2)，但是在如何停止方面有很多经济性和很大的灵活性。