具有彩色边缘的图形中具有最少改变次数的路径

Question

我有一个带有彩色边缘的有向图（红色为&蓝色），可能包含循环。问题是写一个给定两个顶点（s，t）的算法，找到s和t之间颜色变化最小的路径（如果存在这样的路径）。 （我创建了一个新的图，其中每个顶点对应于前一个图的边，并且包含边的颜色，例如：if（1,2）是（1/2）是新图中的一个顶点，我连接了“相邻边”顶点，新图中改变颜色的边的权重为1，同一颜色变换为0 ）。

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

有没有这样的解决方案来找到最小路径？

Answer 1

第一阶段：减少到最短路径问题。

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

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

后您减少问题的最短路径搜索，你可以做到以下几点：

1. 步骤：仅在重0边，处理图形的无向一个与BFS可以帮助以线性时间查找此0边图中的所有组件。

2. 步骤：在图表上运行BFS其中来自前一步骤的部件胶合在一起作为超级节点，因此，所有边缘具有权重1和BFS会发现的最短路径。

显然，这种算法的所有三个部分（在0-边图形BFS，胶合组件以超级节点和在所得到的曲线图中的BFS）中线性时间运行。