algorithm - 枚举不包括两个顶点之间的循环的前 2^20 个路径

Question

输入是一个无向的循环平面图，每个顶点最多有 8 条边。

以从最短到最长的顺序枚举两个顶点 v_0、v_1 之间的所有路径的方法是什么？什么是计算复杂度？

如果以上是不可能的，那么有什么方法可以生成长度不超过 K 的所有路径。

Answer 1

您想获得最长路径的最短路径 -> 表示您可以尝试 BFS。

路径不能包含循环->您应该存储路径已经通过了哪些顶点（当您执行 BFS 时）。

复杂性：您可以看到路径不包含循环意味着路径只能通过每个节点一次。所以解空间是 O(n!) 并且在最坏的情况下 BFS 可能会访问解空间中的每条路径。所以复杂度是 O(n!)。

你可能会对这个结果感到失望。好的，您的问题是一个经过充分研究的著名问题。你可以阅读这篇论文：

Finding the K Shortest Loopless Paths in a Network
Jin Y. Yen

或wikipedia 页面以直观地查看第 K 个最短路径问题。