algorithm - 图中受约束的最短路径

Question

这是我在一个在线法官网站上发现的问题:

我有一个无向图(带循环)。我们在图中有 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(white)->30(blue)->21(white)->22(white)->35(red)->34(black)->40 (goes blue before red)

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

Answer 1

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

图形修改。

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

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

等价。

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

搜索算法。

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

伪代码。

1. currentVertexes = { (source,0) }//顶点和路径长度
2. for i from 0 to sizeof( givenPath ) 做
   1. nextColor = givenPath[ i ]
   2. nextVertexes = {}
   3. for (v,len) in currentVertexes do
      为 所有 你 s.t.存在边e := (v,u) 和 u.color = nextColor
      nextVertexes.insert( (u, len + e.length))
   4. currentVertexes = nextVertexes
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))