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

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

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

\n

使用二分搜索，找到最小尖峰成本 \xce\xb8*，使得 C(\xce\xb8) 为使用具有尖峰成本 \xe2\x89\xa4 \xce\xb8 的边的 st 路径的最小标称成本，我们有 C(\xce\xb8*) = \xce\xb8*。每个解决方案的标称成本或峰值成本至少与 \xce\xb8* 一样大，因此 \xce\xb8* 会导致 2 近似解决方案。

\n

二分搜索中的每个测试都涉及在具有尖峰成本 \xe2\x89\xa4 \xce\xb8 的子集上运行 Dijkstra，因此该算法需要时间 O(|E| log ² |E|)，好吧，如果你想从技术上讲，并使用斐波那契堆，O((|E| + |V| log |V|) log |E|)。

\n