带色边图中最小修改次数的路径

Question

我有一个带彩色边（红色和蓝色）的有向图，它可能包含循环。问题是编写一个给定两个顶点(s，t)的算法，该算法找到s和t之间颜色变化次数最小的路径（如果存在这样的路径）。

我用Dijkstra的一个变体找到了一个解决方案（我创建了一个新图，其中每个顶点对应于前一个图的一条边，并且包含该边的颜色。例如：如果（1,2）是旧图中的一条边，那么（1/2）是新图中的一个顶点。我连接了“相邻边”的顶点，新图中改变颜色的边得到一个权重1，其中相同的颜色转换为0）。

我在寻找（V和E的）线性时间的解。上面的一个在新的图形中使用了VxE边。

有没有这样的解可以找到最小路？

Answer 1

第一阶段：简化为最短路径问题。

1. 对于每个节点i我们创建两个节点i_red和i_blue。
2. 对于每个蓝色边i->j我们创建两个边i_red->j_blue和两个边i_blue->j_blue（权重1和i_blue->j_blue（权重0。
3. 我们以类似的方式处理红边。
4. 我们还需要一个与start_red和start_blue连接的起始节点，连接权重为0。
5. 类似于目标节点，该节点与target_red和target_blue连接，具有权重0-连接。

现在，搜索从新创建的起始节点到新创建的目标节点的最短路径。有两倍于原始图中的节点和两倍于原始图中的边，因此缩减是线性的。

将问题简化为最短路径搜索后,可以执行以下操作：

>

步骤：只使用权重为0的边，将图视为无向图，在bfs的帮助下，可以在线性时间内找到该0边图中的所有分量。

步骤：在图上运行bfs，在图上前面步骤的组件作为超级节点粘在一起，因此所有边都有权重1，并且bfs将找到最短路径。

显然，该算法的三个部分（0边图中的bfs、将组件粘附到超级节点以及结果图中的bfs）都在线性时间内运行。