一种图上两点间最短路径查询方法

摘要

本发明涉及一种图上两点间最短路径查询方法，其步骤包括：1)从图上随机抽取若干点作为支点，根据各支点间的最短路径得出图上每点的中间性估计值；2)将中间性估计值大于设定值的点作为中心点，将图中各点到各中心点的最短路径信息加入图中各点的hop信息，这些中心点的集合记为Wb；3)将图去除Wb中各点后分割为若干小图Si，并得到点割集Ws；4)对于每个小图Si根据枚举出的任意两点间最短路径，得到该小图Si内的所有点的hop信息；5)根据Wb中各点到Ws中各点的最短路径得到不同小图之间的点的hop信息；6)根据图中各点的hop信息，得到用户输入的两查询点之间的最短路径。本发明的方法可行且高效，能在可接受时间内计算出大规模图上的hop信息。

主权项

一种基于数据库中数据集合进行的图上两点间最短路径查询方法，其步骤包括：1）从图上随机抽取若干点作为支点，根据各支点间的最短路径得出图上每点的中间性估计值；2）将中间性估计值大于设定值的点作为中心点及图中各点到各中心点的最短路径信息加入图中各点的hop信息，这些中心点的集合记为Wb；3）将图去除Wb中各点后分割为若干小图Si，1<i≤m，m为小图个数，并得到点割集Ws；4）对于每个小图Si根据枚举出的任意两点间最短路径，得到该小图Si内的所有点的hop信息；所述图中各点的hop信息为四元组<v,u,Dist_sp(v,u),neighbor(v)|_u>，其中，v是大规模数据图上的任意点，u是覆盖v的一条最短路径的中心点，Dist_sp(v,u)是u与v之间的距离，neighbor(v)|_u表示从v到u的最短路径上v的邻居；5）根据Wb中各点到Ws中各点的最短路径得到不同小图之间的点的hop信息；6）根据图中各点的hop信息，得到用户输入的两查询点之间的最短路径，具体操作过程如下：6‑1）当查询两个大规模数据图上的点v₁和v₂之间距离时，对于v₁和v₂分别维护一个hop信息的有序列表，列表中每一项对应一个四元组，列表按照四元组中的中心点的ID的值排序；6‑2）对两个列表进行归并操作，进而得到两点间距离，分别指定两个指针c₁和c₂分别对v₁和v₂的hop信息有序列表进行遍历，当c₁和c₂所指向的四元组的中心点w一样时，将Dist_sp(v₁,w)+Dist_sp(v₂,w)作为v₁和v₂之间距离的候选值；当所有候选值都得到之后，取最小的值即为v₁和v₂之间距离；如果v₁和v₂之间不连通，返回无穷大作为两点间距离；6‑3）计算查询点之间路径时，还需记录v₁和v₂为了取这个候选值所需要途径的邻居结点neighbor(v₁)|_w和neighbor(v₂)|_w，然后迭代地计算neighbor(v₁)|_w和neighbor(v₂)|_w之间的最短路径，直到最后收敛到一个点。