graphdepth-first-searchdijkstragraph-coloringstrongly-connected-graph

Find a path from vertex s to vertex t with minimal number of color alternates

Let $G=(V,E)$ be a directed graph, and let $c:E\mapsto {red,blue}$ be an edge-coloring in red and blue. Let s,t be vertices in G. Find a path from s to t (if exists) so that the number of color changes along this path is minimal.

I have tried to do as follows:

  1. Let $G_r$ be the graph obtained by removing all the blue-colored edges of G. Let $G_b$ be the graph obtained by removing all the red-colored of G.
  2. Let $G_{r}^{SCC}$ be the strongly connected graph of $G_r$, computed using this algorithm.
  3. Let $G_{b}^{SCC}$ be the strongly connected graph of $G_b$, computed using this algorithm.
  4. Color the vertices of $G_{r}^{SCC}$ in red, and color the vertices of $G_{b}^{SCC}$ in blue.
  5. Let $G'=(V',E')$ be the graph obtained by merging $G_{r}^{SCC}$ with $G_{b}^{SCC}$.
  6. Define the weight of each (existing) edge in G' as 0.
  7. For each $(u,v)\in E$ such that u belongs to the strongly connected component $C_u$ and v belongs to the strongly connected component $C_v$ do as follows:
  1. Use Dijkstra algorithm to find a shortest path from the blue strongly connected component of s, to both the blue and red strongly connected components of t.
  2. Use Dijkstra algorithm to find a shortest path from the red strongly connected component of s, to both the blue and red strongly connected components of t.
  3. Let p denote the shortest path among the four we have just found. (namely, p has minimal number of color alternates). p is a series of strongly connected components. Expand each of them using DFS, to find a corresponding path in G.

This algorithm can run in O(E+V*log(v)). Can it be improved or simplified?

Solution

  • I don't fully understand your algorithm, specifically in stage 4 you will color every vertex with two different colored edges in two colors - blue and red...
    Therefor I will not try and improve your algorithm but will present one of my own - a variant of BFS with time of O(E + V).

    The idea: Iterate over the edges of the graph and measure depth as the number of times you switched colors.

    Note: We will run the algorithm twice, first assume that the first edge of the path is red, second assume that the first edge of the path is blue, than take the minimum.

    1. Run BFS only on red edges starting from s (which is the first element in the BFS queue), if you viewed a vertex on a blue edge keep it in a different queue.
    2. Mark all of the nodes you saw with the number i (at the beginning i=0).
    3. Take the queue for the blue edges and make it your primary queue.
    4. Run stages 1 to 3 but switch the colors and add 1 to i.

    At the end the number in t is the minimal number of swaps performed to reach t.