The present specification is directed to systems, components of systems, and methods performed by them, that can find multiple shortest paths in very large graphs.
Graph analysis methods are used to compute a shortest path on a weighted directed graph. A number of techniques for solving shortest paths problems have been implemented. The Dijkstra and the Bellman-Ford algorithms for the single source shortest paths problem have no parallelism and/or are not scalable. While Bellman-Ford can easily be parallelized, it is not scalable because it requires too many iterations, each propagating messages through all the edges. Others' work on parallelizing the Dijkstra algorithm has resulted in system designs that rely on the use of shared memory, random access to in-memory graph data, and reliable machines. Such designs cannot run across many machines, cannot be realized in the absence of shared memory access, cannot work with large graphs stored on disk, and cannot routinely handle machine failures. Examples of such systems are described in “Parallel Shortest Paths Algorithms for Solving Large-Scale Instances”: http://www.cc.gatech.edu/research/reports/GT-CSE-06-19 and http://www.cc.gatech.edu/—bader/papers/ShortestPaths-ALENEX2007.pdf. These systems use shared memory models and where the graph data is all in memory, and are described as working on large graph instances having 2 billion edges.
The systems described in this specification can compute single source and multiple source shortest paths for graph instances having trillions of edges and have the capacity to scale to even larger size graphs.