Study Of Shortest Path Problem On Large-Scale Graph

The shortest path problem is a classical problem both in graph theory and algorithm design. It is also a fundamental problem with numerous applications in the real world, such as route planning, logistics planning, GPS navigation, biomedicine, social networks, Location Based Service (LBS) and so on. Calculating the shortest path from some vertices to others as fast as possible is an urgent demand in these applications. with the development of GPS, electronic map and LBS, location information grows explosively, and the scale of graphs on which shortest path algorithms run becomes larger and larger. Thus traditional algorithms have not met the need of real time, particularly in applications based on road network. Meanwhile, shortest path algorithms keep developing continuously, which is promoted by the requirements of these applications.Despite the research in shortest path problem has achieved tremendous development, existing schemes face big challenges yet. There are three major ways of addressing challenges. The first is to study serial algorithms which are more efficient than previous ones. Pre-computation technology is an efficient approach for this problem. The second is to study approximate algorithms. Exact distances are unnecessary at all in most real scenes. Using approximation distances can reduce the computation complexity significantly. Then the last is to study parallel algorithms. It is an inevitable choice to develop parallel algorithms for fully exploiting the features of modern multicore architecture.This dissertation focuses on improving the performance of shortest path algorithms and carries out the research by following two threads. From a perspective of research content, it studies three common variants of the problem:single source shortest path (SSSP), point-to-point shortest path (P2P), and all-pairs shortest path (APSP) problems. From the other perspective, it proposes several novel serial, approximate and parallel algorithms, which matches the trend of research in this domain. Specifically, the main contents and contributions of this dissertation are as follows.(1) An efficient lower-bounding approach for point-to-point shortest path problem. Finding the shortest path from a source vertex to a sink vertex in real time is an important problem in numerous applications. In the literature, several lower-bounding schemes have been proposed to solve the problem so far, such as A*search and ALT algorithm. But these schemes adopted loose valuations on distance so that there are great potentialities for improving the lower bounds. This dissertation proposes a novel two-stage goal directed lower-bounding approach, called ACT algorithm, which combined A*search, centers and triangle inequality with no prior domain knowledge. Unlike previous schemes, the new algorithm can obtain excellent distance bounds by exploiting a large number of pre-computed data. The experimental results on real road networks show that ACT algorithm significantly outperforms all previous algorithms. In some instances, the vertices scanned by ACT algorithm are only about25%more than those on optimal path.(2) An efficient pre-computation technique for approximation k-Nearest Neighbor (kNN) search in road networks. Processing kNN query in road networks has caught more and more researchers’ attention. This dissertation proposes a simple and efficient pre-computation technique to solve this problem, with loss of some accuracy. This approach chooses a proper representative nodes set R from road network G(V, E)(R is a subset of V) and computes the distance values of any pairs in R which are pre-computed. Since|R|<<|V|, it requires so less memory size that the kNN query can be processed in one common personal computer. Moreover, the approximation of distance value between any pairs in V is well bounded. The experimental results on real road networks showed that this pre-computation technique yielded excellent performance with good approximation guarantee and high processing speed.(3) Optimization of parallel single source shortest path (SSSP) algorithm on OpenCL Heterogeneous computing platform. It is difficult to parallelize traditional shortest path algorithms in straightforward fashion because of the strong data dependency. Heterogeneous computing brings opportunities and challenges to solve this difficulty. This dissertation discusses the memory consistency of OpenCL, studies the procedure of parallel SSSP algorithm based on OpenCL and proposes an enhanced algorithm. The enhanced variant reduces the number of kernel invoking significantly by exploiting some optimization approaches including modifying data structure and using atomic operations. The experimental results showed that the enhanced algorithm usually outperformed the original one by more than a factor of two in running time.(4) Optimization of all-pairs shortest path (APSP) algorithm on large-scale sparse graph. Running Dijkstra’s algorithm repeatedly is mainstream solution to APSP problem on large-scale sparse graph yet. This dissertation studies the relationship between the performance of label-correcting algorithm and the initialization of label. Then it proposes an optimization approach which uses incremental computation to initialize the label array. The proposed optimization technology significantly reduces the number of vertex reentries. The experimental results on large-scale graphs showed that the enhanced variant usually outperformed the original variant by an order of magnitude.