Graph Searching algorithm

Here is the problem:
I have to find a path from the starting point to the destination with following considerations.

In the given graph a point could be either:

(1) A Checkpoint--> this point must be there in the final path calculated
(2) A Mine--> this point should not
be there in the final path calculated
(3) A neutral point--> this point
may/may not be there in the final
path calculated

I need an algorithm for this.

Solution

First remove the mines and make a list of the checkpoints.

Then you'll almost certainly have to do a depth-first or breadth-first search. Which one depends on the graph. I'd suggest trying a breadth-first search, with a decent pruning heuristic. A seeker starts at the starting point, then whenever it has a choice to make it copies itself and goes both ways. It keeps two lists: the checkpoints it's visited, and the neutral nodes it's visited since its last checkpoint. When it visits a neutral node it writes its checkpoint list on the wall, and erases any lists that are subsets of its own. It will terminate itself if it encounters one of the following conditions:

It visits a node already on one of its lists.
It sees a checkpoint list on the wall that is a superset of its own.
~~It arrives at the destination without having visited all the checkpoints.~~

That should be enough to get you started. There are other optimisations (such as removing dead ends) that may be worthwhile, depending on the graph.

(EDIT: scratched that last condition when I saw that it would make some graphs impossible.)