求有向图单源到所有顶点的最大路径数及DFS代码时间复杂度

有向完全图中单源到所有顶点的最大路径数 #

在边数E=V²的有向完全图中（每个顶点到所有顶点包括自身都有一条边），由于你的DFS代码会跳过已访问的顶点（避免路径中出现重复节点），我们只需要考虑简单路径（无重复顶点的路径）：

• 从源点出发的简单路径总数由最长路径（哈密顿路径，遍历所有V个顶点的路径）主导，这类路径的数量为(V-1)!（源点固定后，剩余V-1个顶点可以任意排列）。
• 所有简单路径的总数是长度从1到V-1的路径数量之和：$\sum_{k=1}^{V-1} \frac{(V-1)!}{(V-k)!}$，其渐近复杂度为O(V!)，因为阶乘项是增长最快的部分。

你的DFS代码的时间复杂度 #

你的代码会遍历所有可能的简单路径，每个递归调用会遍历当前顶点的所有V条出边：

• 总共有O(V!)条路径需要探索，每条路径最多包含V个顶点。
• 每个顶点的处理需要遍历V条边，因此总操作数的渐近复杂度为O(V * V!)，简化后可表示为O(V!)（V相对于阶乘增长可忽略）。

注意事项 #

这种暴力遍历所有路径的方法仅适用于极小的V值（比如V<10），因为阶乘增长速度极快（例如V=20时，20!≈2.4×10¹⁸，完全无法在合理时间内处理）。如果你的目标是计算到各顶点的最短路径，建议使用多项式时间算法：

• 若边权非负：使用Dijkstra算法，时间复杂度为O(V² log V)（针对该完全图）。
• 若存在负权边：使用Bellman-Ford算法，时间复杂度为O(V³)。

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