## Algorithm for determining if a path exists in a graph or if not, the closest edit distance.

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

3
for q1, I'm not seeing the problem. given the sequence of nodes in the path, why can't you just verify that directed edges exist between each adjacent pair of nodes ? – Suresh Venkat May 27 2010 at 1:09
good point, I guess q2 is what I'd like know more about. – Deniz May 27 2010 at 3:53

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9380460381507874, "perplexity_flag": "head"}