algorithm - 单源最短双子路径

Question

我正在尝试解决 Sedgewick & Wayne 的算法书中的一个问题:单源最短双调路径。

对于那些不熟悉问题的人的一些定义:

Monotonic shortest-path: a monotonic shortest-path is a shortest-path in which the edges are either strictly increasing or strictly decreasing.

Bitonic shortest-path: a shortest-path from s to t in which there is an intermediate vertex v such that the weights of the edges on the path s to v are strictly increasing and the weights of the edges on the path from v to t are strictly decreasing.

题目思路是:

Given an edge-weighted digraph, find a bitonic shortest path from a given source vertex to every other vertex (if one exists). The path should be simple (no repeated vertices).

到目前为止，我有以下内容:

单调最短路径可以通过按升序放宽图中的所有边(找到升序单调最短路径)或按降序放宽图中所有边(找到降序单调最短路径)来计算最短路径)。

我预先计算了从源顶点到所有其他顶点的升序单调最短路径(这可以在 O(E) 中完成，因为它只是一棵最短路径树)。

然后我预先计算了所有顶点对的降序单调最短路径，因为任何顶点都可以是中间顶点，任何顶点都可以是目标顶点。这需要 O(E * V) 时间。

现在，对于从 s 开始到 t 结束的每条路径，我可以检查 (1) 从 s 到中间顶点 v 的单调升序最短路径和 (2) 从 v 到 v 的降序单调最短路径的所有组合t 并选择权重最低的路径。这会给我一条从 s 到 t 的双调最短路径。

但是，有一个问题:我们不能在路径中有重复的顶点，并且上述想法没有解决这个问题。

对于解决问题的最后一部分有什么想法吗？也欢迎任何其他解决问题的想法/方法。

Answer 1

(注意:我没有检查你的想法的宏伟计划是否真的成立，或者是否有更快的算法。这只解决重复顶点的问题。)

假设递减路径和递增路径都不包含重复顶点，重复顶点的唯一机会是顶点同时存在于“双调”路径的递减和递增部分。

A --1-- B --3-- C --5-- D --7-- E --7-- D --5-- C --2-- F --1-- Z

在此示例中，C 位于路径的两部分中，E 是中间顶点。可以看出，这个也表示从C到E和从E到的段C 在递增和递减路径中必须相同。如果递减路径中有不同的(更短的)路径，则递增路径在通过该节点路由时也会更短。

这意味着，我们可以简单地切断 C 的两个实例之间的段，留下更短的“双调”路径。 (或者，我们可以忽略较长的双调路径，因为我们稍后会找到较短的双调路径，无论如何，当考虑 C 而不是 E 作为中间节点时。)

A --1-- B --3-- C --2-- F --1-- Z

这会导致看似奇怪的结果，例如 A --1-- B --1-- Z，其中两条连续的边具有相同的权重。但是根据您的定义“从 s 到 t 的最短路径，其中有一个中间顶点 v 使得路径 s 到 v 上的边的权重严格增加并且从 v 到 v 的路径上的边的权重t 严格递减”，这应该仍然是双调路径，因为 A --1-- C 和 C --1-- Z 都是严格单调的分别增加和减少。