# Dijkstra's Algorithm with different color nodes

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!

• 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. – hengxin Nov 13 '14 at 5:05

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.

• 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|)? – Eric Nov 13 '14 at 8:22
• @HendrikJan Thanks for the correction! – Yuval Filmus Nov 13 '14 at 14:31
• @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. – Yuval Filmus Nov 13 '14 at 14:32

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}$$).