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

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

作　　者：邵回祖[1] 

机构地区：[1]山西大学工程学院信息工程系,山西太原030013

出　　处：《微计算机信息》2007年第21期236-237,126,共3页Control & Automation

摘　　要：最短路径问题是图论中的一个典范问题,它被应用于众多领域。最短路径问题可以分成两类:单源最短路﹑所有顶点对间的最短路径。在研究图中最短路径问题上,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.

关 键 词：并行算法 多线程技术 最短路径 DIJKSTRA算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]