Which machine learning approach/algorithm do I choose for path validation?
This is a good question but it's rather complicated. I can suggest two approaches:


Graphical models; specifically Bayesian networks since your graph is directed.
Recurrent neural networks. Here's a talk on popular recent model: Sequence to Sequence Learning with Neural Networks.