Find a unique path in a graph that's colored in red and blue

Question

I was given the next assignment:

Let $G=(V,E)$ be an undirected graph and connected,such that every $e\in E$ has a color-blue or red.

Given the same $G$ and some $a,b\in V$ ,construct an efficient algorithm that finds, out of all of the paths with the minimal amount of red edges from $a$ to $b$,a path with the minimal amount of blue edges.

I tried answering but got stuck. Any help will be very appreciated!

• I'm only allowed to use BFS/DFS

Answer 1

I'm assuming you can only use plain vanilla DFS and BFS, and are not allowed to make any modifications to them. Thus, to achieve what you want, you need to modify the behavior of the algorithm by altering the input graph it is running on. Here is a hint on how to find the subgraph of all the paths that connect $a$ and $b$ and contain the smallest possible number of red edges:

Hint:

1. Create a graph $G_\text{blue}$ that contains only blue edges.
2. Using DFS calculate its blue-connected components.
3. Create graph $G_{\text{red}}$ that has these blue-connected components as vertices, and a red edge between any two different components $X$ and $Y$ such that there exist a red edge $(x,y) \in E(G)$ with $x \in X$ and $y \in Y$.
4. Let $V_a$ be the vertex in $G_{\text{red}}$ that corresponds to the blue-connected component of $a$ in $G$.
5. Using BFS calculate the subgraph of shortest paths between $V_a$ and $V_b$ in $G_{\text{red}}$ and let $E'_{\text{red}}$ be the set of edges of $G_{\text{red}}$ that represents that subgraph.
6. Create a directed graph $G'$ from $G$ by filtering the red edges of $G$ so that only edges corresponding to edges in $E'_{\text{red}}$ remain and their direction is matching the BFS layers from the previous point (because $G'$ is directed, each blue edge has to be replaced with two directed arcs).
7. Any path $a \to b$ in $G'$ has now the smallest possible number of red edges (the number of blue edges is not constrained).

I hope this helps $\ddot\smile$

Edit: Added a missing piece of info about the fact that the red edges in (6) should be directed.

Answer 2

On each node $v_i$, keep two counters for the blue and red edges it takes to go from $a$ to $v_i$. Node $a$ starts with $(0,0)$. Do a BFS. Whenever you reach a node, if the counters are undefined, use the previous node, plus $1$ to whichever color edge the graph was, and add the node to the "active search nodes" list. If the counters are defined, and $current_{red} < next_{red} - 1$, set the red and blue counters accordingly. If $current_{red} > next_{red} -1 $ do nothing. If $current_{red} = next_{red} -1 $ use blue as a tie-breaker. When you reach $b$, either find a path backwards or also keep track of paths, depending on whether you want to save time or memory space.