给定图G(V,E)，求从源顶点s到目标顶点d的所有简单路径的复杂度？

这个问题很经典，咱们得从核心本质聊起：简单路径要求无重复节点，而这个问题的复杂度瓶颈完全来自最坏情况下图中存在的路径数量——毕竟要枚举所有路径，首先得面对输出本身的规模。

1. 最坏情况的路径数量 #

在极端图结构里（比如无向完全图、有向完全图），从s到d的简单路径数目是阶乘级的：

• 假设图共有n个节点，s和d是其中两个，剩下n-2个节点。
• 路径可以是：直接s→d（1条）、经过1个中间节点的路径（n-2条）、经过2个中间节点的排列路径（(n-2)*(n-3)条）……直到经过所有n-2个中间节点的全排列路径（(n-2)!条）。
• 把这些路径数加总，总和的量级是O(n!)——这个增长速度比指数级O(2^n)还要快得多。

举个例子：n=4时总共有5条路径，n=5时是16条，n=6时直接跳到65条，规模增长非常迅猛。

2. 时间复杂度 #

因为必须枚举并输出所有路径，所以时间复杂度的下限就是路径总数乘以单条路径的处理成本：

• 每条路径最多包含n个节点，处理/输出一条路径的时间是O(n)。
• 总时间复杂度为O(n * n!)，这是非多项式的阶乘级复杂度。

换句话说，不存在任何多项式时间的算法能解决这个问题——光是输出所有路径的时间就已经是阶乘级了，根本不可能在多项式时间内完成。

另外，如果你只是想计数路径数量（而非枚举），这个计数问题是#P-完全的，难度比NP-难问题更高，因为#P问题需要计算解的总数，而NP仅需判断是否存在解。

3. 空间复杂度 #

空间复杂度分两种场景：

• 如果仅枚举路径不存储结果，空间主要消耗在递归栈（或迭代用的栈）上，最坏情况是O(n)——对应经过所有节点的最长简单路径。
• 如果需要存储所有找到的路径，空间复杂度就是O(n * n!)，因为每条路径占O(n)空间，总共有O(n!)条路径。

总结 #

这个问题的最坏情况复杂度是阶乘级的，无论是时间还是空间（若存储结果）。这是问题本身的输出规模决定的，任何算法都绕不开这个下限。

内容的提问来源于stack exchange，提问作者Shuvra Chakraborty