Shortest path determination for large graphs

摘要

A computer-implemented method and system are provided for determining the shortest path between two nodes in a network comprising a plurality of nodes. A non-transitory computer-readable medium is also provided that includes a plurality of instructions that, when executed by at least one electronic device, at least cause the at least one electronic device to determine the shortest path between two nodes in a network comprising a plurality of nodes.

主权项

1. A computer-implemented method for determining the shortest path between two nodes in a network comprising a plurality of nodes, the method comprising:
receiving a graph comprising at least one node with each node having coordinates for locating the node in a corresponding cell when a grid is laid over the graph; finding connection nodes that are not contained within a cell but are connected with at least one node located in a specific cell; preprocessing the graph by determining the shortest paths between connection nodes for a pair of cells; and searching for the shortest path between any two nodes; wherein the shortest paths between the two nodes will go only through nodes that are involved in the shortest paths between the connection nodes of the two cells in which the two nodes are located.