Given a directed acyclic graph `G` and a path made up from its set of nodes `N`, what is the closest approximate match to N, equipped with an intuitive notion of distance?


A path in a directed acyclic graph is essentially a string (that uses the set of nodes as the alphabet), so when comparing paths one can make use of edit distances developed for approximate string matching:


There are many algorithms for approximate string matching:


<http://en.wikipedia.org/wiki/Approximate_string_matching>


This string matching answers the question when the `G` itself is also a path.. then we're merely asking to compare two strings. 


Asking if an arbitrary graph `A` built from the same set of nodes is a sub-graph of `G` is the general case of the problem, but I'm only interested in the case where `A` is a path and `G` is directed & acyclic.


Any general pointers are also welcome.


-- 


Edit: I ended up using a dynamic programming algorithm, independently also suggested in the accepted answer. Good call! It is probably the most accurate option as well, and barely more "complex" than the string-to-string case when the average # of edges per node is low. 



Algorithm for determining if a path exists in a graph or if not, the closest edit distance.
If graph is acyclic you can use some sort of dynamic programming.
Let $a\_{u,k}$ be the best distance you can get if you start from vertex $u \in G$ and consider only $k$ last vertices of your given path.


It's quite straightforward how to calculate all $a\_{u,k}$ based on all values of $a\_{u',k'}$ with $u'$ "after" $u$ and $k' < k$: you just iterate over all edges going from vertex $u$.


This approach works in $O(|G| \times strlen)$ time.


