图数据库中查询无权图中两点间最短路径的方法及应用
基本信息
| 申请号 | CN201810359289.4 | 申请日 | - |
| 公开（公告）号 | CN108595603A | 公开（公告）日 | 2021-07-02 |
| 申请公布号 | CN108595603A | 申请公布日 | 2021-07-02 |
| 分类号 | G06F17/30 | 分类 | 计算；推算；计数; |
| 发明人 | 洪春涛;朱晓伟;王涛 | 申请（专利权）人 | 深圳神图科技有限公司 |
| 代理机构 | 北京睿邦知识产权代理事务所（普通合伙） | 代理人 | 徐丁峰 |
| 地址 | 100080 北京市海淀区海淀大街3号1幢801室-810L-027 | ||
| 法律状态 | - | ||
摘要
| 摘要 | 图数据库中用于查询无权图中两点间最短路径的长度的方法，假设给定的图为G（V,E），需要查询点a到点b的最短路径，限定的最长跳数为K，则最短路径查询方法包括：（1）比较a侧的潮头和b侧的潮头的大小；（2）选择两侧的“潮头”中的元素数目较小的一侧，以及得到该侧的新潮头；（3）重复上述步骤（1）和（2）直到：查找到一个潮头节点y，它既是a的潮头节点，又是b的潮头节点，此时确定找到最短路径，或者达到其它预定的终止条件；（4）若确定找到最短路径，则确定a，b两点之间最短路径的长度。本发明利用双向搜索，以及基于潮头大小的方向选择，可以大大减少搜索范围，从而可以在大规模的图上高效的执行两点间最短路径查询。 |
