calculate all shortest paths of a network on gpu 05-04-2014d1722

2014-08-29

-All-pairs shortest-paths for large graphs on the GPU
--http://dl.acm.org/citation.cfm?id=1413966
-Efficient Multi-GPU Algorithm for All-Pairs Shortest Paths
--http://hal.inria.fr/docs/00/90/57/38/PDF/APSP_paper_merged.pdf
--"current GPUs support hundreds of cores per chip
and even future CPUs will be many core"
-All-pairs shortest path algorithm based on MPI+CUDA distributed parallel programming model

This paper is not on the gpu, but is still interesting
-A Fast Algorithm to Find All-Pairs Shortest Paths in Complex Networks
{
Finding shortest paths is a fundamental problem in graph theory, which has a large amount of applications in many areas like computer science, operations research, network routing and network analysis. Although many exact and approximate algorithms have been proposed, it is still a time-consuming task to calculate shortest paths for large-scale networks with tremendous volume of data available in recent years. In this paper, we find that the classic Dijkstra's algorithm can be improved by simple modification. We propose a fast algorithm which utilize the preiously-calculated results to accelerate the latter calculation. Simple optimization strategies are also proposed with consideration of characteristics of scale-free complex networks. Our experimental results show that the average running time of our algorithm is lower than the Dijkstra's algorithm by a factor relating to the connection probability in random networks of ER model. The performance of our algorithm is significantly better than the Dijkstra's algorithm in scale-free networks generated by the AB model. The results show that the time complexity is reduced to about O(n2.4) in scalefree complex networks. When the optimization strategies are applied, the algorithm performance is further improved slightly in scale-free networks
}

azim58wiki: