利用多线程技术实现最短路径的并行算法

Based on Java multithreading realization during all apexes most short-path parallel algorithm

最短路径问题是图论中的一个典范问题,它被应用于众多领域。最短路径问题可以分成两类:单源最短路﹑所有顶点对间的最短路径。在研究图中最短路径问题上,Dijkstra算法是其中最为经典的算法之一,本文主要介绍所有顶点对间的最短路径问题,提出了一种更高效的新的所有顶点对间的并行算法。最后利用多线程技术对给出的并行算法进行了实现。

The shortest path question is in a graph theory model question, it is applied in the multitudinous domain. The most shortpath question may divide into two kinds： Simple 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 the end this paper realizes the parallel algorithms in the technology of Java muhithreading.