在加权无向图中，如何在两个节点之间找到固定长度的路径？

Question

我想要一个算法或指针，以进一步研究如何找到一个固定长度的路径之间的两个节点在一个加权无向图。

Answer 1

从给定节点到给定长度的给定节点的简单路径是NP完全的：哈密顿循环问题是这个类的一个问题，它是NP完全的。

如果边是加权的，那么子集和问题就是这个问题的一个特例，所以我们仍然是NP完全的

在这两种情况下，您都可以枚举路径，修剪不简单的路径或在theta（b^len）expected time中过长的路径，其中b是分支因子（平均出度）。

找到允许重复边的路径（有时称为行走）可以通过[length]矩阵乘法完成，总计O（v^3*len）时间复杂度或更好。

让A表示图的邻接矩阵。然后，A^len保存每对顶点之间长度len的路径数。您可以在乘法过程中使用1 1=1（布尔加法-不确定它如何与高级矩阵乘法算法配合使用），这样您只会得到这样一条路径的存在，但同时可以避免整数溢出。

准备A^1。。A^len（O（n^3 len））。然后，对于1中的每个距离d。。len，找到一个顶点v[d]，该顶点是v[d-1]的子节点，并且具有到目标的len-d-长路径（O（n len））。

如果您只需要知道这样一条路径是否存在，那么您不需要a。。A^len，仅A^len。您可以通过平方和乘法算法在时间O（n^3 log（len））中计算，甚至与铜匠威诺格拉德矩阵乘法算法结合时，也可以在时间O（n^2.37 log（len））中计算。

或者，您可以只搜索[node x distance]状态空间，并在O（n*b*len）中完成。