0
$\begingroup$

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
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Lola Please see an update, there was a missing piece of information. $\endgroup$ – dtldarek Mar 22 '18 at 17:32
  • $\begingroup$ Why do they have to be directed? :( $\endgroup$ – Lola Mar 22 '18 at 18:53
  • $\begingroup$ @Lola It is possible to work around that (i.e., they don't have to be directed), but it makes things easier. In the previous version of my answer we could "go back" (in terms of BFS layers from point 5.) and then forward again, thus technically use more red edges (and so the claim that any path would have minimal number of red edges was not true). We use the directed edges to make sure that we never "go back", that is, when you reach a vertex of some BFS layer, you won't be able to make the path return to the lower layer again. $\endgroup$ – dtldarek Mar 22 '18 at 21:00
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I forgot to mention, but I'm only allowed to use BFS or DFS :-( $\endgroup$ – Lola Mar 21 '18 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.