How to find lightest path in directed weighted graph where each edge has a color

Question

We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, Find an efficient algorithm that gives the weight of the lightest path from $s$ to $t$ that satisfies these conditions:

1. If there is a green edge, then there must be a red edge that appeared before the first green edge in the path.
2. If there is a blue edge, then there must be a green and a red edge that appeared before the first blue edge in the path.

Note: it's possible that A path that satisfies these conditions doesn't have all colors in it. For example the lightest path from $s$ to $t$ with 7 red edges in it.

So I think that we must use the Bellman-Ford algorithm after editing $G$ or creating a new graph and using it on it.

• 喜欢算法和数学: As I understand here, it is allowed to visit the same vertex multiple times in a path. In particular, the lightest path could visit a particular vertex multiple times. Otherwise, I doubt there is an efficient algorithm.
• D.W.: Can you share where you encountered this task, or the context or motivation?
• D.W.: I encourage you to credit the original source and original author.
• D.W.: You can credit the exam and its author like any other source: e.g., University of Molbaria, CS 291, Fall 2016 Final exam, Proj. Jane Smith and link to it if a link is available.

Answer 1

Given $G=(V,E,w)$, the new graph you want to build is $H=(V', E', w')$ where:

• $V' = \{\text{target}\} \cup(V \times \{r, g, b\})$
• • $((v, r),(u, r))\in E'$ iff $(v,u)\in E$ is red.
  • $((v, r),(u, g))\in E'$ iff $(v,u)\in E$ is red.
  • $((v, g),(u, g))\in E'$ iff $(v,u)\in E$ is red or green.
  • $((v, g),(u, b))\in E'$ iff $(v,u)\in E$ is green.
  • $((v, b),(u, b))\in E'$ iff $(v,u)\in E$
  • $((t, .), \text{target}) \in E'$
• • For any $e' =( (u,\cdot), (v,\cdot) ) \in E'$, $w'(e') = w(u,v)$.
  • $w'(((t, .), \text{target})) = 0$

In plain words,

• $H$'s vertices are a special vertex, $\text{target}$ and three copies of original vertices, a copy in red, a copy in green and a copy in blue.
• • An edge connects two red vertices iff the (corresponding) edge between the original (uncolored) vertices (exists and it) is red.
  • An edge goes from a red vertex to a green vertex iff the edge between the original vertices is red.
  • An edge connects two green vertices iff the edge between the original vertices is red or green.
  • An edge goes from a green vertex to a blue vertex iff the edge between the original vertices is green.
  • An edge connects two blue vertices iff the edge between the original vertices exists (and its color can be any color).
  • An edge that goes from each colored copy of $t$ to $\text{target}$.
• The weight of a new edge is the same as that of the edge between the original vertices, except the weight of each edge that connects to $\text{target}$ is 0ドル$.

The construction of edges in $H$ ensures that

• from a red vertex, a red edge must be visited before we can reach a green vertex, and
• from a green vertex, a green edge must be visited before we can reach a blue vertex.

A path from $s$ to $t$ in $G$ that satisfies the conditions in the question corresponds to, edge by edge, some path from $(s, r)$ to $\text{target}$ in $H$ and vice versa. Since the weights on each pair of corresponding edges are the same except the edge to $\text{target}$, the weight of which is 0ドル$, the weights of the two paths are the same as well. A valid cycle of negative weight in $H$ (here valid means that cycle can appear in a path satisfying the two conditions) corresponds to a negative cycle in $G$ and vice versa. A shortest path from $s$ to $t$ in $G$ corresponds to some shortest path from $(s,r)$ to $\text{target}$ in $H$ and vice versa.

Now we can apply the Bellman-Ford algorithm on $H$ with source $(s,r)$. The application will be able to detect whether there is a cycle of negative weight. If there is a negative cycle, there is also a valid negative cycle in $G$, and hence there will not be a shortest path. Otherwise, the application will tell the weight of the lightest path from $(s,r)$ to $\text{target}$ in $H$, which is what we wanted, the weight of the lightest path from $s$ to $t$ satisfying the two conditions.

---

If you know the basic theory on finite state machines, read How hard is finding the shortest path in a graph matching a given regular language? and its answer, where you can learn the general strategy.