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

Question

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

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

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

有什么想法吗？现在我正在考虑在图中的每个节点上运行 DFS，这在我看来远未达到最佳状态。

Answer 1

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

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

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