查询子图中的最长路径

提问参考模版:

  • nebula 版本:3.2.1
  • 部署方式:分布式
  • 安装方式:Docker
  • 是否上生产环境:Y
  • 硬件信息
    • 8C40G
  • 问题的具体描述
    有没有找到图中某个点A到叶子节点的最长路径的命令? 我只找到最短路径的命令.
    目前我的思路是遍历所有连接点, 计算出这些连接点和点A的路径然后取最大, 想问下是否有更简单的方法

你期望的结果是最终的点列表?还是路径也要?

要路径 :joy:因为要算最长的路径长度

你这个已经很简单了呀,应该可以满足你的需求吧,你说的最短路径的命令是要指定起点和终点的

如果不要路径明细的话,我目前能想到的一个优化点是去掉p=,直接用size(e)来替代
理论上来说会省一点内存和提升一些性能。

2 个赞

这个需求确实比较新颖,找具体点到“叶子”节点的最长路径。首先这里的“叶子”节点怎么定义?按照以往的认知,叶子结点是只有一条边跟图上其他节点连接。不知这样理解是否正确?

如果图的结构是树形结构,那么找某点到叶子结点的最长路径,跟找其最短路径应该是一致的,这个没有证明,但是从路径中的边不能重复上能够想象是这样。

如果图的结构非树形,那么会存在如下的情况:

A -> B -> E
    / \
   C -> D

现在求 A->E 的路径,有两条 A->B->E 和 A->B->C->D->B->E,如果按照最长路径的需求,那么应该是第二个答案。但是从路径的形状而言,这里有个小环,甚至找某个最长路径可能将图中的所有点都能牵涉进来,这个在我们看来有点不太能理解,不知道这种需求在业务上是什么样的?可否再具体的详细描述一下?谢谢!

2 个赞

是啊, 但是觉得遍历计算图中的每个连通点, 还是有点浪费资源 :joy:

感谢大佬这么详细的询问 :+1: 我来补充一下需求背景吧:
我在做一个关联排黑的项目, 抽象来说就是从一个点A关联出来一个有向无环图, 然后需要求得此有向无环图的最大阶数, 也就是根节点A到叶子节点的最长路径.

谢谢MuYi, 我记下这个技巧了 :grinning:

如果想找有向无环图的话,目前能想到的一个方法是 FIND NOLOOP PATH,可以找出所有从 A 出发到叶子结点的所有路径,然后统计最长的 path 的长度。

此话题已在最后回复的 30 天后被自动关闭。不再允许新回复。