查找两个graphics节点之间的所有path
我正在执行Dijkstrasalgorithm来检索路由networking中互连节点之间的最短path。 我有实施工作。 当我将起始节点传入algorithm时，它将所有节点的最短path返回给所有节点。
我的问题：如何从节点A检索所有可能的path来说节点G，甚至所有可能的path从节点A并回到节点A
find所有可能的path是一个难题，因为存在指数级的简单path。 即使find第k个最短path（或最长path）也是NP-Hard 。
find从s到t所有path[或者所有到达一定长度的path]的一个可能的解决scheme是BFS ，而不保留visited集合或加权版本 – 您可能想要使用统一的成本search
请注意，在每个具有循环的graphics中（不是DAG ），在s到t之间可能会有无数的path。
我会给你一个（有点小）的版本（虽然我认为是可以理解的），这是一个科学certificate，你不可能在可行的时间内做到这一点。
我要certificate的是，枚举任意图G两个选定和不同节点（比如s和t ）之间的所有简单path的时间复杂度并不是多项式。 请注意，由于我们只关心这些节点之间的path数量，边缘成本并不重要。
当然，如果图表有一些很好的select属性，这可以很容易。 我正在考虑一般情况。
假设我们有一个多项式algorithm，列出s和t之间s所有简单path。
如果G连接，则列表不为空。 如果G不是和s和t在不同的组件中，那么列出它们之间的所有path是非常容易的，因为没有！ 如果它们在同一个组件中，我们可以假装整个图只包含该组件。 那么我们假设G确实连接了。
列出的path的数量必须是多项式的，否则algorithm不能全部返回给我。 如果它列举所有这些，它必须给我最长的一个，所以它在那里。 有了path列表，可以应用一个简单的过程来指向这个最长的path。
我们可以certificate（虽然我想不出一个有凝聚力的方式来说），这条最长的path必须遍历G所有顶点。 因此，我们刚刚find一个哈密尔顿path的多项式过程！ 但这是一个众所周知的NP难题。
我们可以得出这样的结论：我们认为这个多项式algorithm是不太可能存在的，除非P = NP 。
我已经实现了一个版本，它基本上find了从一个节点到另一个节点的所有可能的path，但是它不包括任何可能的“周期”（我使用的图是周期性的）。 所以基本上，没有一个节点会在相同的path中出现两次。 如果图是非周期的，那么我想你可以说，似乎在两个节点之间find了所有可能的path。 它似乎工作得很好，对于我的graphics大小〜150，它几乎立即在我的机器上运行，但我确定运行时间必须是指数级的，所以它会开始变慢，因为graphics变大。
这是一些演示我实现的Java代码。 我相信一定有更高效或更优雅的方法来做到这一点。
Stack connectionPath = new Stack(); List<Stack> connectionPaths = new ArrayList<>(); // Push to connectionsPath the object that would be passed as the parameter 'node' into the method below void findAllPaths(Object node, Object targetNode) { for (Object nextNode : nextNodes(node)) { if (nextNode.equals(targetNode)) { Stack temp = new Stack(); for (Object node1 : connectionPath) temp.add(node1); connectionPaths.add(temp); } else if (!connectionPath.contains(nextNode)) { connectionPath.push(nextNode); findAllPaths(nextNode, targetNode); connectionPath.pop(); } } }
这里是一个algorithmfind并打印使用修改的DFS从s到t的所有path。 也可以使用dynamic编程来查找所有可能path的数量。 伪代码将如下所示：
AllPaths(G(V,E),s,t) C[1...n] //array of integers for storing path count from 's' to i TopologicallySort(G(V,E)) //here suppose 's' is at i0 and 't' is at i1 index for i<-0 to n if i<i0 C[i]<-0 //there is no path from vertex ordered on the left from 's' after the topological sort if i==i0 C[i]<-1 for j<-0 to Adj(i) C[i]<- C[i]+C[j] return C[i1]
你通常不想，因为在非平凡的图中有一个指数的数字; 如果你真的想得到所有的（简单的）path或者所有的（简单的）循环，你只要find一个（通过走图），然后回溯到另一个。
我想你想要的是基于BFS的Ford-Fulkersonalgorithm的某种forms。 它用于通过查找两个节点之间的所有增广path来计算networking的最大stream量。
http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
我想你想find'简单'的path（如果没有节点出现在其中，path很简单，除了第一个和最后一个）。
由于问题是NP难题，您可能需要做一个深度优先search的变体。
基本上，从A生成所有可能的path，并检查它们是否以G结尾。
有一篇很好的文章可以回答你的问题/只有它打印的path，而不是收集他们/。 请注意，您可以在在线IDE中尝试C ++ / Python示例。
http://www.geeksforgeeks.org/find-paths-given-source-destination/
find_paths [s，t，d，k]
这个问题现在有点老了，但是我会把我的帽子扔进戒指。
我个人发现find_paths[s, t, d, k]forms的algorithm很有用，其中：
- s是起始节点
- t是目标节点
- d是要search的最大深度
- k是要find的path的数量
使用你的编程语言的d和k的无穷大forms将给你所有的path。
很明显，如果你使用的是有向图，并且你想要在s和t之间s所有无向path，你将不得不以这两种方式运行：
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
帮助函数
我个人喜欢recursion，虽然有时候会困难，反正先定义我们的帮助函数：
def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found) current_path.append(current) if current_depth > max_depth: return if current == goal: if len(paths_found) <= number_of_paths_to_find: paths_found.append(copy(current_path)) current_path.pop() return else: for successor in graph[current]: self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found) current_path.pop()
主function
有了这个，核心function是微不足道的：
def find_paths[s, t, d, k]: paths_found = [] # PASSING THIS BY REFERENCE find_paths_recursion(s, t, 0, d, k, [], paths_found)
首先，让我们注意一些事情：
- 上面的伪代码是语言的混搭，但最像Python（因为我只是编码）。 严格的复制粘贴将不起作用。
-
[]是一个未初始化的列表，将其replace为您select的编程语言的等价物 -
paths_found通过引用传递。 很显然recursion函数不返回任何东西。 正确处理。 - 这里的
graph是假设某种forms的hashed结构。 有很多方法来实现一个graphics。 无论哪种方式，graph[vertex]得到一个有向图中的相邻顶点列表 – 相应地调整。 - 这假定你已经预处理去除“扣”（自循环），循环和多边
