公开(公告)号：US11657091B2

公开(公告)日：2023-05-23

申请号：US16986120

申请日：2020-08-05

Applicant: BEIJING BAIDU NETCOM SCIENCE AND TECHNOLOGY CO., LTD.

Inventor： Le Deng ,  Kunbin Chen ,  Jun Fang

IPC: G06F16/901 ,  G06F16/2455 ,  G06F16/28

CPC classification number: G06F16/9024 ,  G06F16/24558 ,  G06F16/288

Abstract: The present disclosure provides a method and an apparatus for querying the shortest path of a graph, and a storage medium. The method includes: performing a breadth-first search in a distributed graph database with a start entity to be searched and an end entity to be searched as root nodes respectively, and obtaining a layer of new entities for each search; performing an intersection checking on the new entities and entities of the highest layer from a search set on an opposite side, so as to determine whether an intersection between the new entities and the entities of the highest layer exists; and when the intersection exists, determining intersection points, and performing path backtracking through the intersection points to find the shortest path from the start entity to the end entity.