图数据库中查询无权图中两点间最短路径的方法及应用
基本信息
| 申请号 | CN201810359289.4 | 申请日 | - |
| 公开（公告）号 | CN108595603B | 公开（公告）日 | 2021-07-02 |
| 申请公布号 | CN108595603B | 申请公布日 | 2021-07-02 |
| 分类号 | G06F16/901;G06F16/904;G06F16/903 | 分类 | 计算；推算；计数; |
| 发明人 | 洪春涛;朱晓伟;王涛 | 申请（专利权）人 | 深圳神图科技有限公司 |
| 代理机构 | 北京永新同创知识产权代理有限公司 | 代理人 | 林锦辉 |
| 地址 | 518000 广东省深圳市南山区粤海街道滨海社区高新南十道81、83、85号深圳市软件产业基地1栋A1202AC17 | ||
| 法律状态 | - | ||
摘要
| 摘要 | 图数据库中用于查询无权图中两点间最短路径的长度的方法，假设给定的图为G(V,E)，需要查询点a到点b的最短路径，限定的最长跳数为K，则最短路径查询方法包括：(1)比较a侧的潮头和b侧的潮头的大小；(2)选择两侧的“潮头”中的元素数目较小的一侧，以及得到该侧的新潮头；(3)重复上述步骤(1)和(2)直到：查找到一个潮头节点y，它既是a的潮头节点，又是b的潮头节点，此时确定找到最短路径，或者达到其它预定的终止条件；(4)若确定找到最短路径，则确定a，b两点之间最短路径的长度。本发明利用双向搜索，以及基于潮头大小的方向选择，可以大大减少搜索范围，从而可以在大规模的图上高效的执行两点间最短路径查询。 |
