具有彩色边缘的图形中更改次数最少的路径
Path with the minimum number of alterations in graph with colored edgest
我有一个带彩色边（红色和蓝色）的有向图，其中可能包含循环。问题是编写一个给定两个顶点 (s,t) 的算法，该算法找到 s 和 t 之间颜色变化最少的路径（如果存在这样的路径）。
我找到了一个使用 Dijkstra 变体的解决方案（我创建了一个新图，其中每个顶点对应于前一个图的一条边，并包含边的颜色。例如：if (1,2)是旧图中的一条边，然后 (1/2) 是新图中的一个顶点。我连接了 "adjacent edges" 个顶点，新图中改变颜色的边的权重为 1，其中相同的颜色过渡是 0).
我正在寻找线性时间（V 和 E）的解决方案。上面的在新图中使用了 VxE 边。
有没有这种求最小路径的方案？
第一阶段：简化为最短路径问题。
- 对于每个节点
i，我们创建两个节点 i_red 和 i_blue。
- 对于每条蓝色边
i->j，我们创建两条边 i_red->j_blue，权重 1 和 i_blue->j_blue，权重 0。
- 我们以类似的方式处理红色边缘。
- 我们还需要一个与
start_red和start_blue连接的起始节点，连接权重为0。
- 类似于目标节点，与
target_red和target_blue连接，权重为0-connections.
现在，搜索从新创建的起始节点到新创建的目标节点的最短路径。节点数和边数是原始图中的两倍，因此减少是线性的。
将问题简化为最短路径搜索后，您可以执行以下操作：
步骤：仅使用权重为 0 的边，将图视为无向图，借助 bfs，您可以在线性时间内找到此 0 边图中的所有组件。
步骤：运行 图上的 bfs，其中上一步的组件粘合在一起作为超级节点，因此所有边的权重为 1，bfs 将找到最短路径。
显然这个算法的所有三个部分（0 边图中的 bfs，将组件粘合到超级节点和结果图中的 bfs）运行 在线性时间内。
我有一个带彩色边（红色和蓝色）的有向图，其中可能包含循环。问题是编写一个给定两个顶点 (s,t) 的算法，该算法找到 s 和 t 之间颜色变化最少的路径（如果存在这样的路径）。
我找到了一个使用 Dijkstra 变体的解决方案（我创建了一个新图，其中每个顶点对应于前一个图的一条边，并包含边的颜色。例如：if (1,2)是旧图中的一条边，然后 (1/2) 是新图中的一个顶点。我连接了 "adjacent edges" 个顶点，新图中改变颜色的边的权重为 1，其中相同的颜色过渡是 0).
我正在寻找线性时间（V 和 E）的解决方案。上面的在新图中使用了 VxE 边。
有没有这种求最小路径的方案？
第一阶段：简化为最短路径问题。
- 对于每个节点
i，我们创建两个节点i_red和i_blue。 - 对于每条蓝色边
i->j，我们创建两条边i_red->j_blue，权重1和i_blue->j_blue，权重0。 - 我们以类似的方式处理红色边缘。
- 我们还需要一个与
start_red和start_blue连接的起始节点，连接权重为0。 - 类似于目标节点，与
target_red和target_blue连接，权重为0-connections.
现在，搜索从新创建的起始节点到新创建的目标节点的最短路径。节点数和边数是原始图中的两倍，因此减少是线性的。
将问题简化为最短路径搜索后，您可以执行以下操作：
步骤：仅使用权重为 0 的边，将图视为无向图，借助 bfs，您可以在线性时间内找到此 0 边图中的所有组件。
步骤：运行 图上的 bfs，其中上一步的组件粘合在一起作为超级节点，因此所有边的权重为 1，bfs 将找到最短路径。
显然这个算法的所有三个部分（0 边图中的 bfs，将组件粘合到超级节点和结果图中的 bfs）运行 在线性时间内。