找到两个图节点之间的所有路径

Question

找到两个图节点之间的所有路径

我正在研究Dijkstras算法的实现，以检索路由网络上的互连节点之间的最短路径。我有实施工作。当我将起始节点传递给算法时，它返回所有节点的所有最短路径。

我的问题：如何检索从节点A到节点G的所有可能路径，甚至是从节点A返回到节点A的所有可能路径

Answer 1

找到所有可能的路径是一个难题，因为存在指数的简单路径。即使找到第k个最短路径[或最长路径]也是NP-Hard。一个可能的解决方案，从找到的所有路径[或所有路径达到一定长度] s来t为BFS，没有保持visited一套，或加权版本-你可能想使用统一的搜索成本注意，同样在具有周期每图表[它不是一个DAG ]可能存在的路径之间无限多s到t。

Answer 2

我已经实现了一个版本，它基本上找到了从一个节点到另一个节点的所有可能路径，但它没有计算任何可能的“周期”（我正在使用的图形是循环的）。所以基本上，没有一个节点会在同一路径中出现两次。如果图是非周期性的，那么我想你可以说它似乎找到了两个节点之间的所有可能路径。它似乎工作得很好，并且对于我的图形大小~150，它几乎立即在我的机器上运行，虽然我确定运行时间必须是指数的，所以它会开始变得很慢，因为图变大了。这是一些Java代码，演示了我实现的内容。我确信必须有更高效或更优雅的方式来做到这一点。Stack&nbsp;connectionPath&nbsp;=&nbsp;new&nbsp;Stack();List<Stack>&nbsp;connectionPaths&nbsp;=&nbsp;new&nbsp;ArrayList<>();//&nbsp;Push&nbsp;to&nbsp;connectionsPath&nbsp;the&nbsp;object&nbsp;that&nbsp;would&nbsp;be&nbsp;passed&nbsp;as&nbsp;the&nbsp;parameter&nbsp;'node'&nbsp;into&nbsp;the&nbsp;method&nbsp;belowvoid&nbsp;findAllPaths(Object&nbsp;node,&nbsp;Object&nbsp;targetNode)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(Object&nbsp;nextNode&nbsp;:&nbsp;nextNodes(node))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(nextNode.equals(targetNode))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Stack&nbsp;temp&nbsp;=&nbsp;new&nbsp;Stack(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(Object&nbsp;node1&nbsp;:&nbsp;connectionPath) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp.add(node1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;connectionPaths.add(temp); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;if&nbsp;(!connectionPath.contains(nextNode))&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;connectionPath.push(nextNode); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;findAllPaths(nextNode,&nbsp;targetNode); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;connectionPath.pop(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}}

Answer 3

我会给你一个（有点小）的版本（尽管可以理解，但我认为）是一个科学的证明，你不能在可行的时间内做到这一点。我要证明的是，在任意图中枚举两个选定节点和不同节点（例如s和t）之间的所有简单路径的时间复杂度G不是多项式的。请注意，由于我们只关心这些节点之间的路径数量，因此边缘成本并不重要。当然，如果图表具有一些选择良好的属性，这可能很容易。我考虑的是一般情况。假设我们有一个多项式算法，列出s和之间的所有简单路径t。如果G已连接，则列表为非空。如果G不是和s并且t在不同的组件中，列出它们之间的所有路径真的很容易，因为没有！如果它们在同一个组件中，我们可以假装整个图形仅包含该组件。所以我们假设G确实是连通的。所列出的路径数必须是多项式的，否则算法不能全部返回。如果它列举了所有这些，它必须给我最长的一个，所以它就在那里。拥有路径列表，可以应用一个简单的过程指向我这是最长的路径。我们可以证明（尽管我不能想出一种有说服力的方式来表达它），这条最长的路径必须遍历所有的顶点G。因此，我们刚刚找到了一个带有多项式过程的哈密顿路径！但这是一个众所周知的NP难题。然后我们可以得出结论，我们认为我们所拥有的这种多项式算法不太可能存在，除非P = NP。