3
$\begingroup$

You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to determine if a colorful path exists, and if so, find one that contains a minimum number of white nodes.

Im not sure how to get started on this. Any help is greatly appreciated!

$\endgroup$
  • 2
    $\begingroup$ I have an idea, but I am not sure whether it is right. First assign high weights (for example, $\geq$ (n \choose 2)) to the directed edges to white nodes and low weights (for example, $1$) to other directed edges. Then, run Dijkstra algorithm on the directed, weighted graph. $\endgroup$ – hengxin Nov 13 '14 at 5:05
1
$\begingroup$

Expanding on hengxin's idea, in order to find whether such a path exists, go over all choices of two nodes $x,y$, one red and the other blue, and see if there are paths $s \leadsto x \leadsto y \leadsto t$. In order to find the one containing the minimum number of white nodes, assign weight 1 to edges entering white nodes, and weight 0 to all other edges. The weight of a path is now the number of white nodes. Go over all possible choices of $x,y$, and calculate the minimum-weight path $s\leadsto x\leadsto y\leadsto t$; choose $x,y$ that minimize that weight.

$\endgroup$
  • $\begingroup$ Thanks for the help! Quick Question: I know that Dijkstra's algorithm has a complexity of O(|V| + |E| log|V|), if we have weights such as 0 and 1 or just very small weights in general, does the algorithm then have a complexity of O(|V|+|E|)? $\endgroup$ – Eric Nov 13 '14 at 8:22
  • $\begingroup$ @HendrikJan Thanks for the correction! $\endgroup$ – Yuval Filmus Nov 13 '14 at 14:31
  • 1
    $\begingroup$ @Eric I don't think so. The algorithm is anyhow pretty slow, since you need to go over all pairs of non-white vertices of opposite color. Perhaps there is some trick that results in a genuinely faster algorithm. $\endgroup$ – Yuval Filmus Nov 13 '14 at 14:32
1
$\begingroup$

An alternative solution that I believe maintains the same complexity as Dijkstra:

Make a copy $G_{start}$ of $G$ and connect it to two other copies: $G_{red\to blue}$ and $G_{blue\to red}$ such that:

  • All red nodes of $G_{start}$ have a zero cost edge to their equivalent in $G_{red\to blue}$.
  • All blue nodes of $G_{start}$ have a zero cost edge to their equivalent in $G_{blue\to red}$.

Then in turn, connect $G_{red\to blue}$ and $G_{blue\to red}$ to another copy, $G_{end}$, such that:

  • All blue nodes of $G_{red\to blue}$ have a zero cost edge to their equivalent in $G_{end}$.
  • All red nodes of $G_{blue\to red}$ have a zero cost edge to their equivalent in $G_{end}$.

Now put your start node in $G_{start}$ and your end node in $G_{end}$ and apply Dijkstra to the resulting graph. The resulting path will be the shortest path that goes through a red node then a blue node (by going through $G_{start} \to G_{red\to blue} \to G_{end}$), or a blue node then a red node (by going through $G_{start} \to G_{blue\to red} \to G_{end}$).

$\endgroup$

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.