我得到一个有向无环图 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 个最大权重，或者没有）。
在每个状态 …