<p>We can modify <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra's algorithm</a> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-02-27T08:35:31.737Z
I changed the problem to address your concerns. Thanks for answering.
Bruce
CC BY-SA 3.0
2013-02-27T08:45:11.693Z
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
CC BY-SA 3.0
2013-02-27T09:31:09.917Z
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
CC BY-SA 3.0
2013-02-27T08:13:14.597Z
2013-02-27T08:13:14.597Z
polkjh
<p>This problem has been addressed in the paper </p>

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

CC BY-SA 3.0
2013-03-03T16:44:14.967Z
That paper addresses a _much_ more general problem than the one described here.
Jeffε
CC BY-SA 3.0
2013-03-02T14:35:53.163Z
2013-03-02T14:35:53.163Z
user14004
<p>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). </p>

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

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

<p>We have to find the <strong>shortest path</strong> 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.</p>

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

<p>Incorrect:</p>

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

CC BY-SA 3.0
2013-02-27T06:58:31.373Z
Is it allowed to pass a white vertex more than once?
Yoshio Okamoto
CC BY-SA 3.0
2013-02-27T06:59:14.600Z
Yes, that is allowed
Bruce
CC BY-SA 3.0
2013-02-27T07:53:28.067Z
Can red, blue black vertices occur more than once, in the same order? That is, is red-red-blue-black valid?
polkjh
CC BY-SA 3.0
2013-02-27T08:20:13.950Z
No, each colored vertex should be traversed only once.
Bruce
CC BY-SA 3.0
2013-02-28T01:26:20.363Z
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ε
CC BY-SA 3.0
2013-03-01T03:05:56.777Z
Is m the sum of edges and vertices?
Bruce
<graph-theory><graph-algorithms>
Constrained shortest path problem
Bruce
# Constrained shortest path problem

(Asked by: username_0 on 2013-02-27)

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)

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Is it allowed to pass a white vertex more than once?  
> **username_0**: Yes, that is allowed  
> **username_2**: Can red, blue black vertices occur more than once, in the same order? That is, is red-red-blue-black valid?  
> **username_0**: No, each colored vertex should be traversed only once.  
> **username_3**: The naïve solution—construct a larger directed graph and run breadth-first search—runs in $O(km)$ time.  Do you need something faster?  
> **username_0**: Is m the sum of edges and vertices?  

---

## 2 answers

### Answer by username_2 on 2013-02-27. Score: 4 | Accepted answer

We can modify [Dijkstra's algorithm](http://en.wikipedia.org/wiki/Dijkstra%27s_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).

> **Comments:**
> **username_0**: I changed the problem to address your concerns. Thanks for answering.  
> **username_0**: 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."  
> **username_2**: 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.  

---

### Answer by username_4 on 2013-03-02. Score: 1

This problem has been addressed in the paper

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

> **Comments:**
> **username_3**: That paper addresses a _much_ more general problem than the one described here.  

---

