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)