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

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.

Authors:

• Chang-le Lu
• Yong Chen

Keywords:

• Dijkstra algorithm
• parallel algorithms
• multi-thread technology
• most short-path
• ratio.

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.