Using Multi-Thread Technology Realize Most Short-Path Parallel Algorithm

Authors: Chang-le Lu, Yong Chen

Abstract:

The shortest path question is in a graph theory model question, and it is applied in many fields. The most short-path question may divide into two kinds: Single sources most short-path, all apexes to most short-path. This article mainly introduces the problem of all apexes to most short-path, and gives a new parallel algorithm of all apexes to most short-path according to the Dijkstra algorithm. At last this paper realizes the parallel algorithms in the technology of C # multithreading.

Keywords: Dijkstra algorithm, parallel algorithms, multi-thread technology, most short-path, ratio.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060627

References:

[1] Guo-liang Chen. Parallel algorithm design and analysis. Beijing: Higher education publishing house, 2002, 433~434.
[2] Wei-min Yan, Wei-min Wu. Construction of data. Beijing: Qinghua University publishing house, 2001.
[3] Yijie Han, V.Y.Pan,J. H. Reif, Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs, Algorithmica (1997) 17: 399-415.
[4] Hong,Cheng An, Guo-Liang Chen. Parallel programming model and language. Journal of Software, 2002.
[5] Jin-long Ji, Jin-li Zhong. Parallel programming model, language and translation technology. Small microcomputer system, 1995.
[6] Dai-ping Ji, Shou-wen Luo, Xin-yi Zhang. The parallel procedure develops the platform architecture the formalized research. Computer applied research, 2004.
[7] H.M.Deitel, Hao-han Ge,Yong-tao Tang. C # university course. Qinghua University publishing house, 2003.