查询子图中的最长路径

[周偉誠]

提问参考模版：

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

[MuYi-方扬]

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

[周偉誠]

@周偉誠

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

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

[dbacyj]

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

[MuYi-方扬]

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

[yee]

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

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

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

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

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

[周偉誠]

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

[周偉誠]

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

[周偉誠]

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

[yee]

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