US Patent 10521473 Shortest path computation in large networks

Embodiments disclosed herein provide systems, methods, and software for determining the shortest distance between vertices in relatively large graphs. In an embodiment a method includes identifying an original graph comprising a plurality of nodes and a plurality of edges, identifying a plurality of hub nodes from within the original graph, creating a hub matrix comprising the plurality of hub nodes and the shortest distance between the plurality of hub nodes, and determining a shortest distance between the at least two nodes using the original graph and/or the hub matrix.