Re: shortest path with constraints that some nodes can not be on the same pth

If I remember correctly, it is NP-Complete to decide wether you can
find such a feasible path according to the size of the constrains.

You might want to look at this paper to get some hint:

Gabow et al.

"On two problems in generation of program test paths"
IEEE tran on Software Engineering, 1976


regards,
yalding

.