Path with the minimum number of alterations in graph with colored edgest

Question

I have a directed graph with colored edges (red & blue) that may contain cycles. The question is to write an algorithm given two vertices (s,t) that finds the path with the minimal number of color changes between s and t (if such path exists).

I have found a solution using a variation of Dijkstra (I created a new graph where each vertex correspond to an edge of the previous graph, and contains the color of the edge. For example: if (1,2) is an edge in the old graph, then (1/2) is a vertex in the new one. I connected "adjacent edges" vertices, and edges in the new graph that change color got a weight of 1, where same color transition is 0).

I am looking for a solution in linear time (of V and E). The above one uses VxE edges in the new graph.

Is there such solution to find the minimal path?

Answer 1

First phase: Reduction to the shortest path problem.

1. For every node i we create two nodes i_red and i_blue.
2. For every blue edge i->j we create two edges i_red->j_blue with weight 1 and i_blue->j_blue with weight 0.
3. We handle red edges in similar fashion.
4. We also need a start node which is connected with start_red and start_blue with connection weight of 0.
5. Similar to the target node, which is connected with target_red and target_blue with weight 0-connections.

Now, search for the shortest path from newly created start node to the newly created target node. There are twice as many nodes and twice as many edges as in the original graph, so the reduction is linear.

After you reduced the problem to the shortest path search, you could do the following:

1. Step: use only edges with weight 0, treat the graph as undirected one and with help of bfs you can find all components in this 0-edge-graph in linear time.

2. Step: run bfs on the graph where the components from the prior step are glued together as super-nodes, so all edges have weight 1 and bfs will find the shortest path.

Obviously all three parts of this algorithm (bfs in 0-edge-graph, glueing the components to super-nodes and the bfs in the resulting graph) run in linear time.