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

摘要

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