摘要： 与求最短路径问题类似,求前k个最短路径问题也是一个经典的网络优化问题,并被广泛应用于实际。对求前k个最短路径问题的顺序算法和并行算法进行了研究,提出了一种基于ChandyandMisra算法的分布式多线程算法,并成功应用于基于Java实现的通信GIS系统中的自动电路调度。

关键词: 最短路径, GIS, 并行算法, 线程

Abstract: The problem of listing the K-th shortest paths ( for a given integer K>1) is a classical network programming problem as well as the shortest path problem. This paper researches two different types of algorithms: sequential algorithm and parallel algorithm, and puts forward a distributed multithreading algorithm based on Chandy and Misra algorithm, which is applied to the automatic circuit scheduling for the communication GIS system of optical cable.

中图分类号: 

• P208