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

Question

找到两个图节点之间的所有路径我正在研究Dijkstras算法的实现，以检索路由网络上的互连节点之间的最短路径。我有实施工作。当我将起始节点传递给算法时，它返回所有节点的所有最短路径。我的问题：如何检索从节点A到节点G的所有可能路径，甚至是从节点A返回到节点A的所有可能路径

Answer 1

找到所有可能的路径是一个难题，因为存在指数的简单路径。即使找到第k个最短路径[或最长路径]也是NP-Hard。

一个可能的解决方案，从找到的所有路径[或所有路径达到一定长度] s来t为BFS，没有保持visited一套，或加权版本-你可能想使用统一的搜索成本

注意，同样在具有周期每图表[它不是一个DAG ]可能存在的路径之间无限多s到t。

Answer 2

我已经实现了一个版本，它基本上找到了从一个节点到另一个节点的所有可能路径，但它没有计算任何可能的“周期”（我正在使用的图形是循环的）。所以基本上，没有一个节点会在同一路径中出现两次。如果图是非周期性的，那么我想你可以说它似乎找到了两个节点之间的所有可能路径。它似乎工作得很好，并且对于我的图形大小~150，它几乎立即在我的机器上运行，虽然我确定运行时间必须是指数的，所以它会开始变得很慢，因为图变大了。

这是一些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 belowvoid 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();
        }
    }}

Answer 3

我会给你一个（有点小）的版本（尽管可以理解，但我认为）是一个科学的证明，你不能在可行的时间内做到这一点。

我要证明的是，在任意图中枚举两个选定节点和不同节点（例如s和t）之间的所有简单路径的时间复杂度G不是多项式的。请注意，由于我们只关心这些节点之间的路径数量，因此边缘成本并不重要。

当然，如果图表具有一些选择良好的属性，这可能很容易。我考虑的是一般情况。

---

假设我们有一个多项式算法，列出s和之间的所有简单路径t。

如果G已连接，则列表为非空。如果G不是和s并且t在不同的组件中，列出它们之间的所有路径真的很容易，因为没有！如果它们在同一个组件中，我们可以假装整个图形仅包含该组件。所以我们假设G确实是连通的。

所列出的路径数必须是多项式的，否则算法不能全部返回。如果它列举了所有这些，它必须给我最长的一个，所以它就在那里。拥有路径列表，可以应用一个简单的过程指向我这是最长的路径。

我们可以证明（尽管我不能想出一种有说服力的方式来表达它），这条最长的路径必须遍历所有的顶点G。因此，我们刚刚找到了一个带有多项式过程的哈密顿路径！但这是一个众所周知的NP难题。

然后我们可以得出结论，我们认为我们所拥有的这种多项式算法不太可能存在，除非P = NP。