找到从A到Z的所有路径的高效算法？
使用一组这样的随机输入 （20k行）：
AB UZ BA AC ZA KZ AQ DA UK PU UP BY YR YU CR RQ AD QZ 找到从A到Z的所有路径。
- A – B – Y – R – Q – Z.
- A – B – Y – U – Z.
- A – C – R – Q – Z.
- A – Q – Z.
- A – B – Y – U – K – Z.
一个位置在路径中不能出现多次，因此A - B - Y - U - P - U - Z无效。
位置被命名为AAA到ZZZ（为简单起见，此处显示为A – Z）并且输入是随机的，以便可能存在或不存在位置ABC，所有位置可能是XXX（不太可能），或者可能不存在所有位置的可能路径都是“孤立的”。
最初我认为这是未加权最短路径问题的变体，但我觉得它有点不同，我不确定算法在这里是如何应用的。
我目前的解决方案是这样的：
-
预处理列表，以便我们有一个将位置（左）指向位置列表的哈希图（右）
-
创建一个hashmap来跟踪“访问过的位置”。 创建一个列表来存储“找到的路径”。
-
将X（起始位置）存储到“访问位置”散列映射。
-
在第一个hashmap中搜索X，（位置A将在O（1）时间内给出（B，C，Q））。
-
对于每个找到的位置（B，C，Q），检查它是否是最终目的地（Z）。 如果存储，则将其存储在“找到的路径”列表中。 否则，如果“访问位置”散列映射中尚不存在，则现在重新启动到步骤3，该位置为“X”。 （下面的实际代码）
利用这种当前的解决方案，对于所提供的数据 ，将所有 （不是最短的）可能路线从“BKI”映射到“SIN”需要永远 。
我想知道是否有更有效（时间）的方式。 有没有人知道一个更好的算法来找到从任意位置A到任意位置Z的所有路径？
当前解决方案的实际代码：
import java.util.*; import java.io.*; public class Test { private static HashMap<String, List> left_map_rights; public static void main(String args[]) throws Exception { left_map_rights = new HashMap(); BufferedReader r = new BufferedReader(new FileReader("routes.text")); String line; HashMap lines = new HashMap(); while ((line = r.readLine()) != null) { if (lines.containsKey(line)) { // ensure no duplicate lines continue; } lines.put(line, null); int space_location = line.indexOf(' '); String left = line.substring(0, space_location); String right = line.substring(space_location + 1); if(left.equals(right)){ // rejects entries whereby left = right continue; } List rights = left_map_rights.get(left); if (rights == null) { rights = new ArrayList(); left_map_rights.put(left, rights); } rights.add(right); } r.close(); System.out.println("start"); List<List> routes = GetAllRoutes("BKI", "SIN"); System.out.println("end"); for (List route : routes) { System.out.println(route); } } public static List<List> GetAllRoutes(String start, String end) { List<List> routes = new ArrayList(); List rights = left_map_rights.get(start); if (rights != null) { for (String right : rights) { List route = new ArrayList(); route.add(start); route.add(right); Chain(routes, route, right, end); } } return routes; } public static void Chain(List<List> routes, List route, String right_most_currently, String end) { if (right_most_currently.equals(end)) { routes.add(route); return; } List rights = left_map_rights.get(right_most_currently); if (rights != null) { for (String right : rights) { if (!route.contains(right)) { List new_route = new ArrayList(route); new_route.add(right); Chain(routes, new_route, right, end); } } } } }
据我了解你的问题，Dijkstras算法不能按原样应用，因为每个定义的最短路径问题在一组所有可能的路径中找到一条路径。 您的任务是找到所有路径本身。
对Dijkstras算法的许多优化涉及以更高的成本切断搜索树。 您将无法在搜索中切断这些部分，因为您需要所有结果。
我假设你指的是除圆圈之外的所有路径。
算法：
-
将网络泵入2xim数组26×26的布尔/整数。 的FromTo [I，J]。 为现有链接设置1 / true。
-
从第一个节点开始跟踪所有后续节点（搜索链接为1 / true）。
-
将访问过的节点保留在某种结构（数组/列表）中。 由于最大深度似乎是26，这应该可以通过递归来实现。
-
正如@soulcheck在下面写的那样，你可能会考虑削减你所看到的路径。 您可以在arrays的每个元素中保留指向目标的路径列表。 相应地调整破坏条件。
-
rest的时候
- 访问结束节点（存储结果）
- 访问之前访问过的节点时（圆圈）
- 访问已找到目的地所有路径的节点，并将当前路径与该节点中的所有现有路径合并。
性能方面，我投票反对使用散列图和列表，而不喜欢静态结构。
嗯，在重读这个问题时，我意识到节点的名称不能仅限于AZ。 你正在写一些大约20k行，有26个字母，一个完全连接的AZ网络需要更少的链接。 也许你跳过递归和静态结构:)
好的，从AAA到ZZZ的有效名称，数组会变得太大。 因此，您最好为网络创建动态结构。 反问题：关于性能，我的算法需要的popuplate数组的最佳数据结构是什么？ 我投票支持2 dim ArrayList。 任何人？
你提出的是DFS的一个方案，只有回溯。这是正确的，除非你想允许循环路径（你没有指定你是否这样做）。
但是有两个陷阱。
- 您必须密切关注当前路径上已访问过的节点（以消除周期）
- 您必须知道如何在回溯时选择下一个节点，这样当您在当前路径上访问时，您不会在图中的同一子树上下降。
伪代码或多或少如下：
getPaths(A, current_path) : if (A is destination node): return [current_path] for B = next-not-visited-neighbor(A) : if (not B already on current path) result = result + getPaths(B, current_path + B) return result list_of_paths = getPaths(A, [A])
这几乎就是你所说的。
但要小心，因为在完整图中查找所有路径都是非常耗时的时间和内存。
编辑为了澄清，该算法在最坏情况下具有Ω（n！）时间复杂度，因为它必须列出大小为n的完整图形中从一个顶点到另一个顶点的所有路径，并且至少有（n-2）！ forms的路径
您的数据本质上是一个邻接列表 ，允许您构建一个以A对应的节点为根的树。为了获得A和Z之间的所有路径，您可以运行任何树遍历算法。
当然，当你构建树时，你必须确保不引入循环。
我将递归地进行，我将在所有节点对之间构建所有可能路径的列表。
我将首先为所有对（X，Y）构建列表L_2（X，Y），它是从X到Y的长度为2的路径列表; 这是很容易构建的，因为这是你给出的输入列表。
然后我将使用已知列表L_2（X，Z）和L_2（Z，Y）递归地构建列表L_3（X，Y），循环遍历Z.例如，对于（C，Q），您必须尝试L_2（C，Z）和L_2（Z，Q）中的所有Z，在这种情况下，Z只能是R，你得到L_3（C，Q）= {C – > R – > Q}。 对于其他对，你可能有一个空的L_3（X，Y），或者从X到Y可能有很多长度为3的路径。但是在这里建立路径时你必须要小心，因为其中一些必须被拒绝，因为他们有周期。 如果路径具有相同节点的两倍，则拒绝该路径。
然后通过组合所有路径L_2（X，Z）和L_3（Z，Y）为所有对建立L_4（X，Y），同时循环Z的所有可能值。您仍然删除具有循环的路径。
等等……直到你到达L_17576（X，Y）。
这种方法的一个担心是你可能会耗尽内存来存储这些列表。 但是请注意，在计算了L_4之后，你可以摆脱L_3等。当然你不想删除L_3（A，Z），因为这些路径是从A到Z的有效路径。
实现细节：你可以将L_3（X，Y）放在17576 x 17576数组中，其中（X，Y）处的元素是一些存储（X，Y）之间所有路径的结构。 但是，如果大多数元素为空（没有路径），则可以使用HashMap ，其中Pair只是存储（X，Y）的某个对象。 我不清楚L_3（X，Y）的大部分元素是否为空，如果是，则L_4334（X，Y）的情况也是如此。
感谢@Lie Ryan在mathoverflow上指出这个相同的问题 。 我的解决方案基本上是MRA的解决方案; Huang声称它无效，但是通过删除具有重复节点的路径，我认为我的解决方案很好。
我想我的解决方案比蛮力方法需要更少的计算，但它需要更多的内存。 这么多，以至于我甚至不确定在具有合理内存量的计算机上是否可行。