A Fast Algorithm to Find All-Pairs Shortest Paths in Complex Networks

T. M. Chan. All-pairs shortest paths with real weights in O(n3/log n)time. in: Proc. 9thWorkshop Algorithms Data Structures, in: Lecture Notes in Computer Science, vol.3608, Springer, Berlin, 2005, pp.318-324. T.M. Chan. All-Pairs ShortestPathsfor Unweighted Undirected Graphsin o(mn)Time. SODA’06, January 22-26, Miami, FL, 2006 . S. Baswana,V. Goyal,S. Sen. All-Pairs nearly 2-approximate shortest pathsin O(n2polylogn)time. Theoretical Computer Science, vol.410, no.1, pp.84-3, 2009 . J.-T. Tang,T. Wang, andJ. Wang. ShortestPath Approximate Algorithm for Complex Network Analysis. Journalof Software,vol.22, no.10, pp.2279 -2290, 2011 . E.W. Dijkstra. ANote onTwo Problemsin Connexion with Graphs. Numerische Mathematik,vol.1, pp.269-271, 1959 . P. Erd̈os and A.Ŕenyi. On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol.5, pp.17-61, 1960 . R. AlbertandA. -L. Barab́asi.TopologyofEvolvingNetworks: LocalEventsandUniversality.PhysicalReviewLetters,vol.85,no.24,Dec. 2000 . R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, vol.16, no.1, pp.87-90, 1958 . J. B. Orlin, K. Madduri, K. Subramani, and M. Williamson. A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths. Journal of Discrete Algorithms, vol.8, no.2, pp.189-198, June 2010 . A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for A*: Effcient Point-to-Point ShortestPath Algorithms. In Proc. of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX’06), Miami, Florida, USA, pp.129-143, Jan. 2006 . L. Roditty andU. Zwick.On Dynamic ShortestPaths Problems. Algorithmica, March 2010 .(published online). S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, vol.312, no.1, pp.47-4, Jan. 2004 . Y. Han. AnoteofanO(n3/log n)time algorithm for all pairs shortest paths. Information ProcessingLetters,vol.105, no.3, pp. 114-116, 2008 . M. Potamias,F. Bonchi,C. Castillo, andA. Gionis. Fast ShortestPath Distance Estimationin Large Networks. Proc.of the 18thACM Conf. on Information and Knowledge Management (CIKM 2009), HongKong, China, pp.867-876,Nov. 2009 . D.J. Watts,S.H. Strogatz. Collective dynamicsof small-world networks. Nature,vol.393, no.6684, pp.440-442,1998 . A.L. Barab́asi,R. Albert. Emergenceof scalingin random networks. Science,vol.286, no.5439, pp.509-512, 1999 . T. M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. Proc. of the 39th Annual ACM Symposium on Theory of Computing (STOC’07), San Diego, California, USA, pp.590-598, June 2007 .