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

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. Jan 7 at 20:25
• Can you share where you encountered this task, or the context or motivation?
– D.W.
Jan 7 at 21:50
• I encourage you to credit the original source and original author.
– D.W.
Jan 7 at 22:01
• 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.
– D.W.
Jan 7 at 22:05

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.