Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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
2  
The naïve solution—construct a larger directed graph and run breadth-first search—runs in $O(km)$ time. Do you need something faster? –  JɛffE Feb 28 '13 at 1:26
show 1 more comment

2 Answers 2

up vote 4 down vote accepted

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).

share|improve this answer
    
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
1  
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
add comment

This problem has been addressed in the paper

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

share|improve this answer
    
That paper addresses a much more general problem than the one described here. –  JɛffE Mar 3 '13 at 16:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.