Yes, using a shortest path tree [1], it is possible to efficiently (for some definition of "efficient") calculate the best path from a single origin node to all

Yes, using a shortest path tree [1], it is possible to efficiently (for some definition of "efficient") calculate the best path from a single origin node to all destination nodes in the graph. Dijkstra's algorithm is the standard implementation, but is not very amenable to parallel processing. Perhaps unsurprisingly, Google has a framework called Pregel [2] which does parallel graph processing. Their research paper outlines how it can be used to calculate a single-source shortest path tree (in section 5.2) in reasonable time. [1] http://en.wikipedia.org/wiki/Shortest_path_tree http://en.wikipedia.org/wiki/Shortest_path_tree [2] http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf http://www-bd.lip6.fr/ens/grbd2011/extra/SIGMOD10_pregel.pdf