计算从给定顶点到具有已定义 属性 的顶点的最短距离

Question

图论中一个很好理解的问题是计算两个顶点之间的最短距离。

我想要做的是找到从给定顶点到具有特定 属性 值的 最近 顶点的最短距离（这个顶点是，未知）。

例如，找到从V(1)到最近的顶点V(?)的最短距离，其中V(?).property(color)==red。

我之前用过的一种方法是从一个焦点顶点迭代地向外移动，询问沿途每个看不见的邻居是否有 color=red.

我还限制了向外步数的上限以提高效率，即将搜索限制在 k 步邻域。

1. 有没有更好的方法解决这个问题？
2. 如何使用 Gremlin 对此进行编码？ （我主要在 Python 中编写代码，但不确定如何迁移算法）

Answer 1

正如您所说，这是图论中的一个众所周知的问题，并且有许多算法解决了这个问题，例如：Dijkstra 的算法。你可以阅读它们 here.

您还可以找到许多 gremlin 秘诀here，包括一个简单的最短路径算法。

通过改变循环停止条件，相信会给你想要的结果：

g.V(1).repeat(out().simplePath()).until(has('color', 'red')).path().limit(1)