I'm looking for metrics (or even just symmetric dissimilarities) on finite paths in finite digraphs but not finding anything in the literature. Can anyone point me to references?
I've looked in Deza and Deza's Encyclopedia of Distances to no avail. Google Scholar has not been helpful.
I know of two obvious things to consider: (say Levenshtein) edit distance on the underlying sequences of vertices or arcs; and graph edit distance on the digraphs corresponding to the paths. In the case of edit distance on a sequence of vertices, we can consider the replacement cost to be given by an underlying metric on digraphs: with this in mind, I am aware of recent work developing metrics on digraphs and Markov chains, e.g. https://arxiv.org/abs/2006.14482. But I am not aware of any treatments of the edit distances themselves, or indeed treatments of any dissimilarities on paths in digraphs.
