图数据库中查询无权图中两点间最短路径的方法及应用

摘要

图数据库中用于查询无权图中两点间最短路径的长度的方法，假设给定的图为G(V,E)，需要查询点a到点b的最短路径，限定的最长跳数为K，则最短路径查询方法包括：(1)比较a侧的潮头和b侧的潮头的大小；(2)选择两侧的“潮头”中的元素数目较小的一侧，以及得到该侧的新潮头；(3)重复上述步骤(1)和(2)直到：查找到一个潮头节点y，它既是a的潮头节点，又是b的潮头节点，此时确定找到最短路径，或者达到其它预定的终止条件；(4)若确定找到最短路径，则确定a，b两点之间最短路径的长度。本发明利用双向搜索，以及基于潮头大小的方向选择，可以大大减少搜索范围，从而可以在大规模的图上高效的执行两点间最短路径查询。