Method and apparatus for querying shortest path of graph, and storage medium
US11657091B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 5, 2020 |
| Grant date | May 23, 2023 |
| Priority date | — |
| Expiry date | May 21, 2041 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/288
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.