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

• 作者: 邵回祖
• 来源期刊: 科技与创新
• 关键词: 并行算法 多线程技术 最短路径 Dijkstra算法
• 年，卷（期）: 2007,（21）
• 所属期刊栏目: 软件时空
• 页码范围: 236-237,126
• 页数: 3页
• 分类号: TP312
• 语种: 中文
• DOI: 10.3969/j.issn.1008-0570.2007.21.096

摘要

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