查找两个graphics节点之间的所有path

我正在执行Dijkstrasalgorithm来检索路由networking中互连节点之间的最短path。 我有实施工作。 当我将起始节点传入algorithm时,它将所有节点的最短path返回给所有节点。

我的问题:如何从节点A检索所有可能的path来说节点G,甚至所有可能的path从节点A并回到节点A

find所有可能的path是一个难题,因为存在指数级的简单path。 即使find第k个最短path(或最长path)也是NP-Hard 。

find从st所有path[或者所有到达一定长度的path]的一个可能的解决scheme是BFS ,而不保留visited集合或加权版本 – 您可能想要使用统一的成本search

请注意,在每个具有循环的graphics中(不是DAG ),在st之间可能会有无数的path。

我会给你一个(有点小)的版本(虽然我认为是可以理解的),这是一个科学certificate,你不可能在可行的时间内做到这一点。

我要certificate的是,枚举任意图G两个选定和不同节点(比如st )之间的所有简单path的时间复杂度并不是多项式。 请注意,由于我们只关心这些节点之间的path数量,边缘成本并不重要。

当然,如果图表有一些很好的select属性,这可以很容易。 我正在考虑一般情况。


假设我们有一个多项式algorithm,列出st之间s所有简单path。

如果G连接,则列表不为空。 如果G不是和st在不同的组件中,那么列出它们之间的所有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的数量

使用你的编程语言的dk的无穷大forms将给你所有的path。

很明显,如果你使用的是有向图,并且你想要在st之间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]得到一个有图中的相邻顶点列表 – 相应地调整。
  • 这假定你已经预处理去除“扣”(自循环),循环和多边