使用HugeGraph怎么求解最短路径？

[huxiaoqing0704]

使用HugeGraph怎么求解最短路径，是通过gremlin的语法实现吗，还是有直接的java api.

[javeme]

hugegraph提供了最短路径的Restful API shortestpath，其URL地址形如：http://localhost:8080/graphs/hugegraph/traversers/shortestpath 详见traverser文档3.1.1 Shortest Path： https://hugegraph.github.io/hugegraph-doc/clients/restful-api/traverser.html

当然hugegraph也支持通过gremlin来实现最短路径：

g.V("src_v_id")
 .repeat(out().simplePath()).until(hasId("target_v_id")
 .or().loops().is(gte(4))).hasId("target_v_id")
 .path().limit(1)

其中src_v_id，target_v_id替换为查询顶点的ID，gte(4)表示做大深度为4，可以根据数据量大小进行调整。

[huxiaoqing0704]

@javeme 非常感谢您的回答，我这边还有以下几个疑问：

1、您gremlin的那个实现，如果做最大深度为4以内的，方向是both的，是不是应该下面的写法？我看您那个中间是用的or()，是不是应该是and()？再就是您那个是gte(4)，是不是应该是lte(4)？

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(1)

2、使用hugegraph的Restful API查询最短路径的性能跟grelin的性能对比一样吗？哪个更好一些？这两种不同的调用方式，底层最短路径的算法实现是一样的吗？

[javeme]

@huxiaoqing0704

如果做最大深度为4以内的，方向是both的，是不是应该下面的写法？

是的，使用both()替换out()即可。

我看您那个中间是用的or()，是不是应该是and()？再就是您那个是gte(4)，是不是应该是lte(4)？

方法until()的含义是直到条件满足则停止，上述给出gremlin语句的意思是：只要找到目标顶点或者到达深度为4则停止。所以应该使用or和gte。更多gremlin说明可参考Tinkerpop官网。

使用hugegraph的Restful API查询最短路径的性能跟gremlin的性能对比一样吗？哪个更好一些？

建议使用Restful API的shortestpath，其性能好于gremlin方式的实现，当然gremlin方式则更加通用。两者的底层实现原理是一样的。

[huxiaoqing0704]

@javeme 非常感谢您的答复。我还有几个问题需要咨询一下： 1、我现在使用gremlin做最短路径查询，使用withRemote方式连接gremlin-server，发现数据量100w+的时候查找最短路径就很慢了，想请教一下，影响最短路径的查询性能有哪些因素？gremlin-server的内存设置大小有关系吗？或者还有别的哪些因素？ 2、如果使用gremlin的方式查找最短路径，HugeGraph和Titan DB、Janusgraph这块儿性能是不是一样的？ 3、查找最短路径的底层实现原理能说明一下吗？这块儿数据是加载到内存中计算吗？

[huxiaoqing0704]

@javeme 之前的这个语句是拿一条最短路径，如果拿全部的最短路径怎么实现？ g.V("src_v_id") .repeat(both().simplePath()).until(hasId("target_v_id") .and().loops().is(lte(4))).hasId("target_v_id") .path().limit(1)

[javeme]

@huxiaoqing0704 多条最短路径可以增加limit的数，-1为不限制。

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(10) // 10条最短路径

[ZhiqinYang]

@huxiaoqing0704 多条最短路径可以增加limit的数，-1为不限制。

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(10) // 10条最短路径

这个不是全部最短路把， 这个查询的因该是 4度以内的全部可达路径吧

[javeme]

多条最短路径可以增加limit的数，-1为不限制。

g.V("src_v_id")
 .repeat(both().simplePath()).until(hasId("target_v_id")
 .and().loops().is(lte(4))).hasId("target_v_id")
 .path().limit(10) // 10条最短路径

这个不是全部最短路把， 这个查询的因该是 4度以内的全部可达路径吧

@huxiaoqing0704 是最短路径的，可以使用小图进行验证看看效果。

[zhoney]

Close this issue now due to having not been updated in a long time. Feel free to reopen it if needed.

[fgz00]

@javeme @ZhiqinYang 向高手请教一下：如何在一个语句中实现1个点到多个目标点的最短路径？（一个起点，多个终点，到每个终点的最短路径）如何在这个上面扩展啦？ g.V("src_v_id") .repeat(both().simplePath()).until(hasId("target_v_id") .and().loops().is(lte(4))).hasId("target_v_id") .path().limit(1)

[sun361504834]

同问如何在一个gremlin语句中实现1个点到多个目标点的最短路径？

@javeme @ZhiqinYang 还有我关注到新版本Traverser模块支持Multi Node Shortest Path来查找指定顶点集两两之间的最短路径，但当我指定MultiNodeShortestPathRequest.builder.step().direction(Direction.BOTH);方向为双向时，返回的查询结果里只有点信息【1:josh, 1:marko, 1:vadas】，我如何把路径里的方向信息也带出来呢？ 举例: 查询1:josh, 1:vadas两个点的最短路径。返回结果【1:josh, 1:marko, 1:vadas】，实际图里的关系存的是 1:josh -> 1:marko和 1:vadas->1:marko。 如何得到方向箭头信息？