基于有向图的路径搜索方法及系统、介质和计算机系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110941735A(43)申请公布日2020.03.31(21)申请号201811120900.4(22)申请日2018.09.25(71)申请人北京京东尚科信息技术有限公司地址100195北京市海淀区杏石口路65号西杉创意园四区11号楼东段1-4层西段1-4层申请人北京京东世纪贸易有限公司(72)发明人范亮(74)专利代理机构中科专利商标代理有限责任公司11021代理人吕雁葭(51)Int.Cl.G06F16/56(2019.01)权利要求书2页说明书11页附图9页(54)发明名称基于有向图的路径搜索方法及系统、介质和计算机系统(57)摘要本公开提供了一种基于有向图的路径搜索方法，用于搜索从目标起点到目标终点的路径，包括：获取包含有目标起点和目标终点的第一有向图的有向图数据；确定第一有向图中各有向边的边配载，其中，一条有向边的边配载用于表征经由该条有向边所能够到达的终点；基于各有向边的边配载，过滤第一有向图，得到保留有经由之后能够到达目标终点的有向边的第二有向图；基于第二有向图，搜索得到从目标起点到目标终点的路径；以及输出表征所述路径的路径数据。本公开还提供了一种基于有向图的路径搜索系统，一种计算机系统和一种计算机可读存储介质。CN110941735ACN110941735A权利要求书1/2页1.一种基于有向图的路径搜索方法，用于搜索从目标起点到目标终点的路径，所述方法包括：获取包含有所述目标起点和所述目标终点的第一有向图的有向图数据；确定所述第一有向图中各有向边的边配载，其中，一条有向边的边配载用于表征经由该条有向边所能够到达的终点；基于所述各有向边的边配载，过滤所述第一有向图，得到保留有经由之后能够到达所述目标终点的有向边的第二有向图；基于所述第二有向图，搜索得到从所述目标起点到所述目标终点的路径；以及输出表征所述路径的路径数据。2.根据权利要求1所述的方法，其中，所述基于所述各有向边的边配载，过滤所述第一有向图，得到保留有经由之后能够到达所述目标终点的有向边的第二有向图，包括：基于所述各有向边的边配载，过滤所述第一有向图，得到保留有界于所述目标起点和所述目标终点之间且经由之后能够到达所述目标终点的有向边的第三有向图。3.根据权利要求2所述的方法，其中，所述基于所述各有向边的边配载，过滤所述第一有向图，得到保留有界于所述目标起点和所述目标终点之间且经由之后能够到达所述目标终点的有向边的第三有向图，包括：基于所述各有向边的边配载，确定不包含与所述目标终点关联的标识的边配载对应的所有的第一有向边；从所述第一有向图中滤掉所述所有的第一有向边；以及将所述第一有向图滤掉所述所有的第一有向边后的剩余部分作为所述第三有向图。4.根据权利要求2所述的方法，其中，所述基于所述各有向边的边配载，过滤所述第一有向图，得到保留有界于所述目标起点和所述目标终点之间且经由之后能够到达所述目标终点的有向边的第三有向图，包括：基于所述各有向边的边配载，提取包含有与所述目标终点关联的标识的边配载对应的所有的第二有向边；确定仅包含所述所有的第二有向边的第四有向图；以及将所述第四有向图作为所述第三有向图。5.根据权利要求2所述的方法，其中，所述方法还包括：确定所述第三有向图中各有向边的边分组信息，其中，有向边的边分组信息用于表征从同一节点出发且边配载相同的有向边集合的相关信息；基于所述第三有向图，搜索从所述目标起点到所述目标终点的路径，包括：基于所述各有向边的边分组信息，搜索所述第三有向图以确定从所述目标起点到所述目标终点的路径。6.一种基于有向图的路径搜索系统，用于搜索从目标起点到目标终点的路径，所述系统包括：获取模块，用于获取包含所述有目标起点和所述目标终点的第一有向图的有向图数据；第一确定模块，用于确定所述第一有向图中各有向边的边配载，其中，一条有向边的边配载用于表征经由该条有向边所能够到达的终点；2CN110941735A权利要求书2/2页过滤模块，用于基于所述各有向边的边配载，过滤所述第一有向图，得到保留有经由之后能够到达所述目标终点的有向边的第二有向图；搜索模块，用于基于所述第二有向图，搜索得到从所述目标起点到所述目标终点的路径；以及输出模块，用于输出表征所述路径的路径数据。7.根据权利要求6所述的系统，其中，所述过滤模块还用于：基于所述各有向边的边配载，过滤所述第一有向图，得到保留有界于所述目标起点和所述目标终点之间且经由之后能够到达所述目标终点的有向边的第三有向图。8.根据权利要求7所述的系统，其中，所述过滤模块包括：第一确定单元，用于基于所述各有向边的边配载，确定不包含与所述目标终点关联的标识的边配载对应的所有的第一有向边；过滤单元，用于从所述第一有向图中滤掉所