公开(公告)号：US20210089580A1

公开(公告)日：2021-03-25

申请号：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

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.