Constrained shortest path in a graph

Question

Here is my problem I found in an online judge website:

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)

10->20(white)->35(red)->56(red)->21(white)->22(white)->30(blue)->34(black)->40 (goes through red twice)

Due to the additional constraints, the shortest path may go through the same vertex twice. For example 20(white)->35(red)->20(white)->30(black). Is this allowed? — Henry
Is there any constraint available for vertex quantity ? If yes please add it, it may have critical importance for solving online judge problem — Grigor Gevorgyan
No constraint on vertex size. Colored vertex should be traversed only once though. — Bruce

Grigor Gevorgyan Grigor Gevorgyan · Accepted Answer · 2013-02-27T10:05:43

I can suggest an O(n*(n+m)) solution based on a simple graph modification completed with a bfs modification. Let me describe it step by step.

Graph modification.

To avoid any troubles, color source and white vertexes in some unique color.
Make graph weighted. Weight of originally present edges is 1.
For each pair of colored vertexes u, v add an edge (u,v) which has a weight equal to the shortest white path from u to v. A white path is a path which passes only over white vertexes. If there is no such white path, don't add an edge.
Remove all white vertexes and their adjacent edges.

The second point can be accomplished by running a bfs from each vertex that passes only over white vertexes. This will run in O( n*(n+m)).

Equivalence.

Now we have a weighted colored graph without white vertexes, and it's easy to see that the problem remains unchanged after modification - we still have to find a shortest path (now in terms of edges weight sum) from source to target vertex.

Search algorithm.

To solve the problem on this graph, run a variation of bfs, which layers correspond the provided path's colors. This means, if you're given path red->blue->black, the first moves bfs will do into all red vertexes adjacent to source, then to all blue adjacent to those red marked, then to all black adjacent to those blue marked, and finally to the target. When some vertex is pushed into bfs queue, remember the length of path to it for future use.

Pseudocode.

currentVertexes = { (source,0) } // vertex and path length
for i from 0 to sizeof( givenPath ) do
1. nextColor = givenPath[ i ]
2. nextVertexes = {}
3. for (v,len) in currentVertexes do
  for all u s.t. exists edge e := (v,u) and u.color = nextColor
  nextVertexes.insert( (u, len + e.length))
4. currentVertexes = nextVertexes
choose the minimum of lengths stored in currentVertexes, as there are only (target, length) pairs.

Complexity:

Graph modification takes O(n*(n+m)) running time and the second part will run O(n*n), because the length of given path can be no longer than n (there's no color duplicates as said in statement), and on each step there can be at most n vertexes in currentVertexes. Total complexity is O(n*(n+m)) + O(n*n) = O(n*(n+m))

Constrained shortest path in a graph

3 Answers