Dijkstra最短路径算法的优化及其实现

被引：40

作者：

王志和 ^{[1
]}

凌云 ^{[2
]}

机构：

[1] 湖南人文科技学院数学系

[2] 长沙学院计算机教学中心

来源：

微计算机信息 | 2007年 / 33期

基金：

湖南省自然科学基金;

关键词：

最短路径; Dijkstra算法; 优化; 配对堆;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用,对其进行优化很有必要。本文分析了传统的最短路径算法(即Dijkstra算法)的优化途径及现有的优化算法,然后在Dijkstra算法的基础上,采用配对堆结构来实现路径计算过程中优先级队列的一系列操作,经理论分析与实验测试结果对比,可以大大提高该算法的效率和性能。

引用

页码：275 / 277

页数：3