为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

慕运维8079593 2019-08-02 14:31:09
找到两个图节点之间的所有路径我正在研究Dijkstras算法的实现,以检索路由网络上的互连节点之间的最短路径。我有实施工作。当我将起始节点传递给算法时,它返回所有节点的所有最短路径。我的问题:如何检索从节点A到节点G的所有可能路径,甚至是从节点A返回到节点A的所有可能路径
查看完整描述

3 回答

?
天涯尽头无女友

TA贡献1831条经验 获得超9个赞

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

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

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


查看完整回答
反对 回复 2019-08-02
?
慕妹3242003

TA贡献1824条经验 获得超6个赞

我已经实现了一个版本,它基本上找到了从一个节点到另一个节点的所有可能路径,但它没有计算任何可能的“周期”(我正在使用的图形是循环的)。所以基本上,没有一个节点会在同一路径中出现两次。如果图是非周期性的,那么我想你可以说它似乎找到了两个节点之间的所有可能路径。它似乎工作得很好,并且对于我的图形大小~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();
        }
    }}


查看完整回答
反对 回复 2019-08-02
?
精慕HU

TA贡献1845条经验 获得超8个赞

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

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

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


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

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

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

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

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


查看完整回答
反对 回复 2019-08-02
  • 3 回答
  • 0 关注
  • 2047 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信