algorithm - 问题：通过首选顶点的最少路线

Question

我需要帮助来解决这个问题：

您有一个图 G=(V,E) ，节点对 s ≠ t ∈ V 并且您有节点的子集 U ⊆ V 存在 ø ≠ U ≠ V 和 s,t ∉ U。对于每条路径 P，我们将其标记为 L (P) 路径的长度（路径中的边数）和#P(U) 路径中节点 U 的数量，编写一个算法来找到从 s 到 t 之间的路径，该路径应该恰好访问 U 2 次以及所有这些轨道的最小长度。换句话说，算法应该返回一条从 s 到 t 的路径，其中 #P(U)=2，假设我们有另一条从 s 到 t 的路径 P'，其中 #P'(U)=2 然后 L(P)≤ L (P') (允许轨道不止一次通过某个顶点)。帮助：使用图形缩减 G'

标签： algorithmgraph-algorithm

Answer 1

将轨迹划分 {s} ∪X → U → X∪ {ε} → U → X∪ {t} where X = V \\ (U∪ {s, t}) (X为 V 中的 5 步顶点组，这些顶点不是首选顶点，既不是 s 也不是 t)，这将确保 #P (U) = 2，我们将使用 BFS 找到最短路径。

算法 - 从 G (V, E) 构造新的有向图 G ^ '= (V ^', E ^ ') 如下：每个首选顶点 u∈U，我们向 V ^ '添加两次，所以 u_4∈V ^'， u_2∈V^'。我们将 s 和 t 添加到新图中，对于每个 x∈X 顶点，我们将在新图中创建 x_1、x_3、x_5。

For each arc (s, x) ∈E | x∈X, {(s, x_1)} ∈E ^ '
Per arc (s, u) ∈E | u∈U, {(s, u_2)} ∈E ^ '
For each arc (x, u) ∈E | x∈X, u∈U, {(x_1, u_2), (x_3, u_4)} ∈E ^ '
Per arc (u, x) ∈E | u∈U, x∈X, {(u_2, x_3), (u_4, x_5)} ∈E ^ '
Per arc (u, u ') ∈E | u, u'∈U, {(u_2, u_4 ^ ')} ∈E ^'
Per arc (u, t) ∈E | u∈U, {(u_4, t)} ∈E ^ '
For each arc (x, t) ∈E | x∈X, {(x_5, t)} ∈E ^ '

我们现在将从 s 开始在图 G 上运行 BFS 扫描。对于 t 在扫描中的第一次出现，从 s 到 t 的轨迹（在降低标签以使 G 中有轨迹之后）是满足问题条件的最短轨迹。如果在扫描中没有找到 t - 那么就没有这样的轨迹。算法的正确性 - #P (U) = 2 - 通过定义图 G '，我们保证从 s 到 t 的每条轨迹将恰好在 U 的顶点中经过两次（这可以通过将顶点标记到阶段 1 中看出-5 和总是分阶段进行的弧线，不可能跳过有 U 顶点的阶段 2 和 4）。最短路径 - 使用 BFS 扫描确保接受最短路径，

最后，降低标签以确保路线在 G 中。算法的复杂性 - 通过遍历 G 的所有顶点和弧一次来构造图 G'，因此在 Θ (m + n) 中运行，扫描 BFS在 G' 在 Θ (m + n) 中运行（通过 BFS 运行时），我们得到运行时的总数为 Θ (m + n)。