Find shortest path that goes through at least 5 red edges

Question

Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges are colored in red (let's say that the rest are colored in blue).

I want to find an efficient algorithm that find the shortest path between $s$ and $t$ that goes through at least 5 different red edges.

Notice that going more than once through the same red edge is still considered as going through 1 red edge in the path.

One idea that I had was creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$. That means that if we go through some red edge $e$, then the path will "move" to a variation of $G$ where $e$ is colored in blue and all the rest is the same.

However in this solution I will have to copy each node and each edge around 400 times. This will result in the same complexity asymptotically, but with such a big constant it seems really not efficient.

Another idea, was to somehow build the new graphs "on the run" of Bellman-Ford algorithm, but I don't really know how to do it.

I'll appreciate some help.

Answer 1

What about reducing the problem first ?

UPDATED with more details :

1. Build 2 node subsets:

   • Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 nodes set.
   • Vt contains t and the 10 sources nodes of the red edges (called b1, b2, ..., b10 hereafter). This is another 11 nodes set.

2. Build a distance matrix M from Vs to Vt (11x11)

3. Do 11 Dijksta explorations, one starting from any node of Vs to reach all nodes of Vt. So you get 11 shortest distances to report in the matrix M. The diagonal terms are irrelevant (s->t or ak->bk).

4. For each row of M, add wi (the weight of the red edge) to all elements (0 for s row). This is the price of crossing the red edge.

5. Build an new graph G' with 11 nodes. node N0 for s&t and nodes Nk for each red edge (ak & bk). Then create all edges using matrix entry: w(Ni -> Nj) = M[i][j].

6. Now your initial problem is equivalent to find a loop of 6 nodes containing N0 in G'. Use any method to test all combinatoric for instance Apass.Jack one. This step in NP complete.

Answer 2

Here is the golden rule of dynamic programming. Adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. In other words, when you cannot move from smaller subproblems to a larger subproblem because of a missing condition, add another parameter to represent that condition.

What is the extra condition here? At least 5 different red edges out of the given 10 edges have to be included in the path. Since there are 10 edges, we will add 10 parameters. Since each parameter has only two values, included or not_included, we can use one number to represent the value of those 10 parameters. That is, a number $0\le s\le 1023$, $$ s = s_0 + s_12+s_22^2+s_32^3+s_42^4+s_52^5+s_62^6+s_72^7+s_82^8+s_92^9$$ where $s_i=1$ if the path does include $i$-th red edge and $s_i=0$ otherwise.

What is the subproblem here? Find the length of shortest path with signature $s$ between two vertices, where $s=(s_0,s_1, \cdots, s_9)\in \{0,1\}^{10}$.

If there is no negative-weighted edges, a straightforward adaptation of Dijkstra's algorithm starting from $s$ will work for these subproblems. The answer will be the minimum among the shortest path with signature $a$ between $s$ and $t$ where at least 5 bits of $a$ are set to 1.

If there are negative-weighted edges, we will consider adapt the Floyd–Warshall algorithm. The details will not be included in this answer.

Note that the above suggestion only leads to the weight (length?) of shortest path. To find the actually path, we have to add another parameter to record the previous node that leads to the current shortest path of certain signature.

---

What Yuval suggested in his comment should be, I believe, essentially the same as what I have abstracted as the golden rule of dynamic programming. In fact, this answer is roughly to confirm the idea in the question, "creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$". Hopefully the implementation here together with some bit twiddling might be easier and faster.