Yep. I see now. Sorry. What if you just "unfold" you graph to explicitly create all possible paths? For example, in your example you should duplicate node D to D1 and D2 and remove edge (D2->G):
_C _ F o| //|\ o / / o / / A---->B------> D1/o o o >G | /\ \ D2 \ \ ^ \ \ \ | \ \ _\| | _\||/ E | H I
Yes, I've yet do it. But the graph can increases his dimension in memory too much; moreover, I must do the "vertex split" ( D in D1 and D2 ) offline, that is before I use the graph in the client application; if the edge's property (that explains in which edge the exploration can go) change, I must change the graph on-the-fly, and my "split algorithm" is complex... I search a strategy to understand in that direction to continue the exploration maintaining the graph unchanged. If there were a way to encapsulate the exploration rule, this would be a more flexible strategy. Best regards, Cosimo Calabrese.