关系数据库环境下图中最短路径的查询方法

摘要

本发明提供一种在关系数据库环境下图中最短路径的查询方法，其步骤包括：将图存储于关系数据库中，按照该图中边的权重将该图对应的表划分成若干子表；根据查询请求中的源结点与目标结点建立已访问结点表，并初始化需要拓展的子表；采用宽度优先搜索方法对各个结点在选定的子表上进行迭代拓展；迭代拓展终止后，继续在原图的所有边上进行一次补充拓展，得到最短路径。本发明将一个大图划分成多个子图，分别存储在不同的数据库表中，使得查询拓展可以在较小的表上进行，能够获得更好的规模性和查询效率。

主权项

一种关系数据库环境下图中最短路径的查询方法，其步骤包括：1)将图存储于关系数据库中，按照该图中边的权重将该图对应的表划分成若干子表；2)根据查询请求中的源结点与目标结点建立已访问结点表，并为源结点和目标结点初始化需要拓展的子表；3)采用宽度优先搜索方法对图中各个结点在选定的子表上进行迭代拓展；所述迭代拓展为双向拓展，进行双向拓展时，所述已访问结点表中的每个结点u包含如下属性：nid，表示结点u的标识符id；d2s，表示结点u距离源结点s当前的最短距离；p2s，表示结点u到源结点s当前最短路径上的前一个结点；fwd，用来引导结点u进行向前拓展时应选择的子表；初始化源结点的fwd为1，在第i次拓展之后，所有新拓展的结点的fwd设置为i+1；d2t，表示结点u距离目标结点t当前的最短距离；p2t，表示结点u到目标结点t当前最短路径上的下一个结点；以及bwd，用来引导结点u进行向后拓展时应选择的子表；初始化源结点的bwd为1，在第i次拓展之后，所有新拓展的结点的bwd设置为i+1；所述迭代拓展包含三种操作：F操作：该操作从已访问结点中选出边界结点进行拓展，如果一个结点未在所有子表上完成拓展，则选其为边界结点；对于正向拓展，若当前是第i次拓展，则边界结点的fwd满足i‑fwd+1小于等于子表的数目；对于反向拓展，若当前是第j次拓展，则边界结点的bwd满足j‑bwd+1小于等于子表的数目；E操作：该操作拓展选出来的边界结点，得到新拓展的结点，每次拓展只为边界结点选择一个子表进行拓展；对于正向拓展，若当前是第i次拓展，则为边界结点选择的拓展子表为第i‑fwd+1个子表；对于反向拓展，若当前是第j次拓展，则为边界结点选择的拓展子表为第j‑bwd+1个子表；M操作：该操作合并新拓展出的结点与之前已访问的结点；判断所述迭代拓展终止的方法为：在第一次拓展完成后，以表示新拓展的结点中具有的最小d2s；对于后续的每次正向拓展，采用迭代计算的方法，等于其中W_unit表示划分的权重单位，min(d2s)表示第i次正向拓展的结点中最小的d2s；在第一次拓展完成后，以表示新拓展的结点中具有的最小d2t；对于后续的每次反向拓展，采用迭代计算的方法，等于其中W_unit表示划分的权重单位，min(d2t)表示第j次反向拓展的结点中最小的d2t；以minCost表示每次拓展完成后当前发现的最短距离，则当时，终止拓展；4)所述迭代拓展终止后，继续在原图的所有边上进行一次补充拓展，得到最短路径。