algorithm - 是否存在满足以下条件的图算法？

Question

N 个节点的图，其中 V = {0, 1, 2, ..., N}

该图的所有边都具有方向属性，例如向上、向北等，因此被引导。该图相对稀疏。

顶点在三个维度上排列，并且边都是等长的(即向左然后向上移动相当于向上然后向左移动，如果两条路径都是可能的)相邻顶点可能有也可能没有边。

找到一系列以节点 J 结束的定向移动，对于所有能够到达 J 的顶点，该移动以 J 结束

所以，问题是:

这是什么类型的图问题？这个是怎么分类的？我真诚地怀疑这个问题的独特性，我想在用病态的算法解决问题之前对其进行分类。

谢谢。

编辑:一个例子是 8 个节点排列成立方体的角。假设沿着立方体的每条边都有两条反平行的图边(两个方向上的方向边)。因此，如果我们说 J 在西南角的立方体的“下”平面中，那么向下、向西、向南移动将到达 J 对于任何能够到达 J 的顶点，包括从 J 本身开始。

Answer 1

我不太确定我理解你的问题，但你为什么不使用从 J 开始的 BFS 并始终沿与边缘暗示相反的方向移动？将找到 J 可到达的任何顶点(就原始方向而言)，并且您将获得一系列移动(以相反的顺序构建)。更重要的是，您将获得的路径将是最短路径(因为所有边的权重相等)。

时间复杂度尽可能低:O(E)(无论如何你都必须构建图)。

关于你问的分类问题:只是一个图搜索问题。