1
$\begingroup$

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

Given $G$ and some $s,t\in V$ ,find an efficient algorithm that find from all pathes from $s$ to $t$,one with an even amount of red edges,and minimal amount of blue edges.

For the part of the even amount of red edges,I know that I can split the vertices,$v$ to $v_o,v_e$ for odd or even amount of red edges till I reached that vertex.

But I'm not sure,how to do the part with the blue edges?

I could give some weight to the blue edges (and red 0 weight) and use Dijkstra's algorithm,but there is a solution in $O(|E|+|V|)$.

Any ideas?

$\endgroup$
  • $\begingroup$ If you're thinking Dijkstra's algorithm, then you must think this is a shortest-paths problem. Do you know any other algorithms for finding shortest paths? $\endgroup$ – D.W. Apr 16 '17 at 17:25
  • $\begingroup$ @D.W. You mean like BFS,DFS? $\endgroup$ – ChikChak Apr 16 '17 at 17:28
  • $\begingroup$ This is your exercise, so I'm going to let you figure out how to solve it. I encourage you to spend some more time on it and see what you can come up with. $\endgroup$ – D.W. Apr 16 '17 at 17:30
  • $\begingroup$ @D.W. ok,but will you give me a hint?do I need to modify BFS/DFS in the solution? $\endgroup$ – ChikChak Apr 16 '17 at 18:14
  • $\begingroup$ I think D.W. is pushing you in the right direction. Do not think what to do at first glance (e.g., whether to modify BFS/DFS or any other algorithm). Instead recognize the key components of your problem to figure out how to do it. D.W. already told you an important one: according to your intuition if you use weights then this problem can be seen as a Shortest Path Problem (SPP). Note however, there is an additional component, and it is that candidates are constrained to have an even amount of red edges. Question is: what SPP algorithm(s) you know that could handle constraints, and how? $\endgroup$ – Carlos Linares López Apr 16 '17 at 23:11

Your Answer

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

Browse other questions tagged or ask your own question.