How to find the lightest path that has at least one vertex of each color?

Question

I've faced this question in my homework.

In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color.

We're given a directed graph $G=(V,\ E)$, weight function $w:E\rightarrow \mathbb{N}^+$ (in other words the weights are positive) and every vertex is colored one of $\{r,g,b\}$. We're required to find the lightest colored path from a given vertex $s\in V$ to every $v\in V$ (including $s$ itself). Such a path may not be simple. If such a path doesn't exist then the lightest path equals $\infty$.

I solved this problem where edges instead of vertices are colored. The problem where vertices are colored is harder in my opinion.

It is clear we have to use Dijkstra's algorithm.

I thought of a possible solution of splitting every vertex to two vertices and then adding an edge between these two copies but the problem is still with the edges between the main vertices which we can't decide which color to give them.

Answer 1

Let $P$ be all non-empty subsets of $\{r,g,b\}$, i.e., $$P=\{\{r\},\{g\},\{b\},\{r, g\},\{r,b\},\{g,b\},\{r,g,b\}\}.$$

Build a weighted directed graph $H=(V', E', w')$ where:

• $V' = V \times P$
• $E'= \left\{((u, \alpha), (v, \beta))\mid (u,v)\in E \text{ and }\beta=\alpha\cup\{\text{the color of } v\} \right\}$
• $w'((u, \alpha), (v, \beta)) = w(u,v)$.

In plain words, for $H$,

• The vertices are seven copy of original vertices with each copy colored a combination of $r, g, b$. The color combination will be used to track the colors of the visited vertices in a path.
• If there is an edge from $u$ to $v$ in $G$, then for every color combination, there is an edge from $u$ of that color combination to $v$ of the color combination that extends that color combination with the color of $v$. In other words, we include the color of $v$ into the visited-color combination when we travel from $u$ to $v$.
• The weight of an edge is the same as the given weight of the edge between the vertices in $G$ ignoring the colors.

Now we can apply Dijkstra's algorithm on $H$ with source $(s,\{\text{the color of } s\})$ and destination $(v, \{r,g,b\})$. With the second component, the color combinations ignored, the result becomes the shortest colored path between $s$ and $v$ in $G$.

---

This answer is quite similar to this answer to another question of yours. The general idea is to keep track of the additional requirement such as the order of colors traversed so far or all colors traversed so far in one or more additional parameters, or, in the terminology of this answer, in a finite state machine.