我有一个有向图，其中有两条有向路径。
我想要一个算法来确定两个路径之间的相似性。
这篇文章提到使用Levenshtein距离来确定近似的相似性。我还意识到汉明距离使用了类似的度量。
我的问题是:如何处理两条路径平行运行的情况?也就是说，如果两条路径没有相似的节点，那么它们将被认为是"相似的"，因为它们的路径在相同的方向上运行，彼此非常接近。
谢谢
简单的回答是，这是一个非常困难的问题，并且在很大程度上依赖于你对图表中"相似"的定义。在大多数图中，你可以以平面的方式重新排列两条不相交路径的节点，使其看起来是"平行的"。
开始研究更高级的相似度指标的一个好地方是考虑图的邻接矩阵，并查看各种矩阵相似度算法。
编辑:限制问题到欧几里得图
在限制欧几里得图的领域时，对这个问题有很多积极的研究，因为这是一个适用于GIS，机器学习应用于机器人，以及社交网络/人工网络(如web)上的协同过滤等领域的主题。查看google scholar上的文章