0
$\begingroup$

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)

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I changed the problem to address your concerns. Thanks for answering. $\endgroup$
    – Bruce
    Feb 27, 2013 at 8:35
  • $\begingroup$ 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." $\endgroup$
    – Bruce
    Feb 27, 2013 at 8:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – polkjh
    Feb 27, 2013 at 9:31
1
$\begingroup$

This problem has been addressed in the paper

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

$\endgroup$
1
  • $\begingroup$ That paper addresses a much more general problem than the one described here. $\endgroup$
    – Jeffε
    Mar 3, 2013 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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