algorithm - 在无向图中查找所有节点之间的所有简单路径的最省时方法

Question

为了扩展标题，我需要一个非常大的无向图中所有节点之间的所有简单（非循环）路径。

我能想到的最明显的优化是，一旦我计算了一对特定节点之间的所有路径，我就可以将它们全部反转，而不是在我需要走另一条路时重新计算。

我正在研究传递闭包和 Floyd-Warshall 算法，但如果我沿着这条路线走，我能做的最好的事情就是只找到所有节点之间的最短路径。

有任何想法吗？现在我正在考虑在图中的每个节点上运行一个 DFS，在我看来这显然不是最佳的。

Answer 1

我不明白您认为 DFS 远不如最优的想法背后的原因。事实上，DFS 在这里显然是最优的。

如果您遍历图，仅将分支限制为到目前为止尚未在此分支中访问过的顶点，则 DFS 树中的节点总数将等于从起始顶点到所有其他顶点的简单路径数顶点。由于所有这些路径都是输出的一部分，因此无法对算法进行有意义的改进，因为您无法将复杂性降低到输出大小以下。

根本没有办法在多项式时间内输出阶乘数据，无论问题是什么或您使用的是什么算法。