1

这是我在在线法官网站上发现的问题：

我有一个无向图（带循环）。我们在图中有 k 个不同类别的顶点。您可以将第 1 类顶点着色为绿色，将第 2 类顶点着色为红色，依此类推。还有一类特殊的白色顶点（稍后会详细介绍）。

现在，用户将指定一个源顶点、一个目标顶点和一系列不同的顶点类（非白色），例如。

我们得到源顶点 10、目标顶点 40 和一个序列：红色->蓝色->黑色。

我们必须找到最短路径，使得该路径从顶点 10 开始，接触 1 个红色顶点，然后是 1 个蓝色顶点和 1 个黑色顶点，然后到达顶点 40。但是，该路径可以根据需要具有任意数量的白色顶点。它还可以遍历一个白色顶点两次。

所以一个解决方案可以是：10->20(white)->35(red)->21(white)->22(white)->30(blue)->34(black)->40

不正确：

10->20（白色）->30（蓝色）->21（白色）->22（白色）->35（红色）->34（黑色）->40（先变成蓝色再变成红色）

10->20(白)->35(红)->56(红)->21(白)->22(白)->30(蓝)->34(黑)->40(穿过红两次）

4

3 回答 3

2

我可以建议一个基于简单图形修改的O(n*(n+m))解决方案，该修改完成了 bfs 修改。让我一步一步地描述它。

图形修改。

  1. 为了避免任何麻烦，颜色源和一些独特颜色的白色顶点。
  2. 使图形加权。最初存在的边的权重是1。
  3. 对于每对彩色顶点u, v添加一条边(u,v)，其权重等于从 u 到 v 的最短白色路径。白色路径是仅通过白色顶点的路径。如果没有这样的白色路径，则不要添加边缘。
  4. 删除所有白色顶点及其相邻边。

第二点可以通过从每个仅通过白色顶点的顶点运行bfs来完成。这将在 O(n*(n+m)) 中运行。

等价。

现在我们有了一个没有白色顶点的加权彩色图，很容易看出修改后问题仍然没有改变——我们仍然需要找到从源顶点到目标顶点的最短路径（现在就边权重而言）。

搜索算法。

要解决此图上的问题，请运行 bfs 的变体，哪些层对应于提供的路径颜色。这意味着，如果给定路径 red->blue->black，bfs 的第一个移动将移动到与源相邻的所有红色顶点，然后移动到与标记的红色相邻的所有蓝色，然后移动到与标记的蓝色相邻的所有黑色，最后到达目标。当某个顶点被推入 bfs 队列时，记住它的路径长度以备将来使用。

伪代码。

  1. currentVertexes = { (source,0) } // 顶点和路径长度
  2. 对于i从0到 sizeof ( givenPath )做
    1. nextColor = givenPath[ i ]
    2. 下一个顶点= {}
    3. for (v , len) in currentVertexes 对 所有u st 存在边e := (v,u)和u.color = nextColor nextVertexes .insert( (u, len + e.length))

    4. 当前顶点=下一个顶点
  3. 选择存储在currentVertexes中的最小长度，因为只有 (target, length) 对。

复杂：

图形修改需要O(n*(n+m))运行时间，第二部分将运行O(n*n)，因为给定路径的长度不能超过 n （声明中没有颜色重复） ，并且在每一步中， currentVertexes中最多可以有 n 个顶点。总复杂度为O(n*(n+m)) + O(n*n) = O(n*(n+m))

于 2013-02-27T10:05:43.867 回答
1

您可以使用带有附加标志的 dijkstra 算法来显示顶点的路径是否满足条件。

于 2013-02-27T06:49:42.373 回答
1

假设 A1（稍后解除）：序列 S 中不存在两次颜色。

然后我们可以使用以下算法 B1：

  1. 在有向图 G' 中按以下方式变换图 G：
    • G' 与 G 有相同的节点
    • 如果 v 是一个白色节点并且 (v,u) 存在于 G 中，则将 (v,u) 和 (u,v) 插入 G'
    • 如果 (v,u) 存在于 G 中并且 (color(v),color(u)) 存在于 S 中，则在 G' 中插入 (v,u)
    • G 的所有其他边（包括循环）都被忽略。
  2. 为所有边分配相同的权重
  3. 在 G' 上执行最短路径算法，例如 Bellman-Ford

现在我们放宽 A1：假设 A2：在 S 中只有一种颜色存在不止一次

算法 B2：

  1. wl.og, c0 是在 S 中多次存在的颜色，更准确地说是 n 次。
  2. 将 S 分成子序列 S1, S2, ... 其中 S1=(c1,c2,...,c0), S2=(c3,...,c0)...
  3. 针对每个 S_i，通过关于 B1 的步骤 1. 的变换 G 生成图 G1、G2、...
  4. 通过连接 G1、G2、... Gn 形成图形 G'
    • 将 G1 中颜色 c0 的每个节点与颜色 c3 的每个节点和 G2 中的任何白色节点连接起来
    • 对 G2 和 G3 等做同样的事情。
  5. 应用 G1 中的源和 Gn 中的目标的最短路径算法

扩展到序列中的几个重复颜色：

将序列拆分为没有重复颜色的序列，并类似地应用 B2。

于 2013-02-27T08:06:37.097 回答