枚举前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 pages获得第K个最短路径问题的直观视图。