1
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
0

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.