# Constrained shortest path problem

Here is my problem: I have an undirected graph (with loops). We have k different classes of vertices in the graph. You can think of class 1 vertex being colored green, class 2 vertices colored red and so on. There is also a special class of vertices colored white (more later).

Now, the user will specify a source vertex, a destination vertex, and a sequence of distinct vertex classes (non-white) eg.

We are given source vertex 10, destination vertex 40, and a sequence: red->blue->black.

We have to find the shortest path such that the path starts from vertex 10, touches 1 red vertex followed by 1 blue and 1 black vertex and then reaches vertex 40. The path, however, can have as many white vertices as needed. It can also traverse a white vertex twice.

So a solution can be: 10->20(white)->35(red)->21(white)->22(white)->30(blue)->34(black)->40

Incorrect:

10->20(white)->30(blue)->21(white)->22(white)->35(red)->34(black)->40 (goes to blue before red)

• Is it allowed to pass a white vertex more than once? – Yoshio Okamoto Feb 27 '13 at 6:58
• Yes, that is allowed – Bruce Feb 27 '13 at 6:59
• Can red, blue black vertices occur more than once, in the same order? That is, is red-red-blue-black valid? – polkjh Feb 27 '13 at 7:53
• No, each colored vertex should be traversed only once. – Bruce Feb 27 '13 at 8:20
• The naïve solution—construct a larger directed graph and run breadth-first search—runs in $O(km)$ time. Do you need something faster? – Jeffε Feb 28 '13 at 1:26

We can modify Dijkstra's algorithm to solve this problem too. For each vertex, in Dijkstra's algorithm, we store the shortest path to that vertex obtained so far. Here, we store $r+1$ different shortest paths per vertex (where the required colour sequence is $c_1,c_2,\ldots ,c_r$). In each vertex, the first path corresponds to shortest path so far, containing only whites. And for $i=1,2,\ldots ,r$, $(i+1)^{th}$ path is the shortest path so far, that contains vertices of colours $c_1,c_2,\ldots ,c_i$ (in that order) mixed with white vertices.

While modifying shortest paths for the new node, we will modify all $r+1$ paths if it is white and if it is of a different colour $c$, only those $(i+1)^{th}$ paths are modified which have $c_{i+1}=c$. And when the algorithm ends, the $(r+1)^{th}$ path in each vertex gives the required shortest path to that vertex.

Complexity will be $r$ times the complexity of Dijkstra's. Note that we have not assumed the colours in the sequence to be distinct (so we can get shortest paths with required sequence as red-black-red-blue too). Also, we can easily modify this to allow multiple vertices of same colour to occur together (i.e., red-red-black-blue can be considered same as red-black-blue).

• I changed the problem to address your concerns. Thanks for answering. – Bruce Feb 27 '13 at 8:35
• How do you ensure that the ordering is maintained in "And for i=1,2,…,r, (i+1)th path is the shortest path so far, that contains vertices of colours c1,c2,…,ci (in that order) mixed with white vertices." – Bruce Feb 27 '13 at 8:45
• We maintain the ordering by modifying only selected paths when adding a new vertex. Let $v$ be the current node and $u$ be an adjacent node. If $u$ is white, we can add it to any path without violating ordering. So we add $w(v,u)$ to each path in $v$, and replace the corresponding path in $u$ if this new path is shorter. But if $u$ has colour $c$, then we can use only use those paths in $v$ for which the next colour in the sequence is $c$ (i.e., $(i+1)^{th}$ path is considered if $c_{i+1}=c$ and this can replace $(i+2)^{th}$ path in $u$). The remaining paths in $u$ are kept same as earlier. – polkjh Feb 27 '13 at 9:31

This problem has been addressed in the paper

Formal language constrained path problems by Barrett et al. SIAM Journal on Computing, 2000, Vol 30.

• That paper addresses a much more general problem than the one described here. – Jeffε Mar 3 '13 at 16:44