一种改进的Dijkstra算法的分析及程序实现

doi:10.3969/j.issn.1006-2475.2011.01.010

计算机与现代化 ›› 2011, Vol. 1 ›› Issue (1): 36-3.doi: 10.3969/j.issn.1006-2475.2011.01.010

一种改进的Dijkstra算法的分析及程序实现

郝春梅

哈尔滨金融学院计算机系，黑龙江哈尔滨 150030

收稿日期:2010-10-08 修回日期:1900-01-01 出版日期:2011-01-20 发布日期:2011-01-20

Program Implementation and Analysis on an Improved Dijkstra Algorithm

HAO Chun-mei

Computer Science Department, Harbin University of Finance, Harbin 150030, China

Received:2010-10-08 Revised:1900-01-01 Online:2011-01-20 Published:2011-01-20

摘要/Abstract

摘要：

Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法。本文通过对传统的Dijkstra算法进行分析，提出一种改进算法，经理论分析，对于顶点数较多而边数较少的有向稀疏图来说，在求最短路径时能够大大提高算法的运行效率。

关键词: 最短路径, Dijsktra算法, 改进算法

Abstract:

Dijkstra algorithm is an algorithm for solving singlesource shortestpaths of directed graph.This paper analyzes classical Dijkstra algorithm and puts forward an improved algorithm. By theoretical analysis, the improved algorithm can improve efficiency of directed sparse graph.

Key words: shortestpath, Dijkstra algorithm, improved algorithm

郝春梅. 一种改进的Dijkstra算法的分析及程序实现[J]. 计算机与现代化, 2011, 1(1): 36-3.

HAO Chun-mei. Program Implementation and Analysis on an Improved Dijkstra Algorithm[J]. Computer and Modernization, 2011, 1(1): 36-3.

[1]	韩雪. 基于约束聚类和粒子群算法的多路径规划[J]. 计算机与现代化, 2023, 0(08): 7-11.
[2]	黄翼虎, 于亚楠. 基于改进Dijkstra算法的防冲突最短路径规划研究[J]. 计算机与现代化, 2022, 0(08): 20-24.
[3]	李月，陈丽，王槐彬. 基于改进联合相似度计算的图书推荐算法[J]. 计算机与现代化, 2019, 0(03): 85-.
[4]	刘飞. 基于最短路径和最大模块度融合的社团发现算法[J]. 计算机与现代化, 2017, 0(5): 19-23.
[5]	林家祺,卢罡,许南山. 一种基于路径阻断的求解最短路径算法[J]. 计算机与现代化, 2017, 0(12): 6-11.
[6]	叶青1,2，胡昌标1,2. 一种改进的基于图论的图像分割方法[J]. 计算机与现代化, 2016, 0(9): 64-67.
[7]	雷玉梅. 基于改进遗传算法的大规模TSP问题求解方案[J]. 计算机与现代化, 2015, 0(2): 34-.
[8]	王兴，祝维聪，张皓，张潇潇. 融合天气监测与预报的出行线路规划算法[J]. 计算机与现代化, 2015, 0(2): 25-.
[9]	唐彩红. 基于方向优先和对向搜索的改进Dijkstra算法[J]. 计算机与现代化, 2014, 0(7): 113-116.
[10]	崇昊旻;陈合. 基于树分解结构的Top-k最短路径查询算法[J]. 计算机与现代化, 2013, 1(5): 10-15.
[11]	王一松;王直杰. 基于实时交通信息的最优路径规划算法研究[J]. 计算机与现代化, 2013, 1(2): 52-55.
[12]	陈萱华;杨玲;李学亚. 最短路径算法在自动测评系统中的应用[J]. 计算机与现代化, 2012, 208(12): 1-3,7.
[13]	丁硕;巫庆辉. 基于改进BP神经网络的函数逼近性能对比研究[J]. 计算机与现代化, 2012, 1(11): 10-13+1.
[14]	李冉冉. 基于蚁群算法的交通流诱导设计与实现[J]. 计算机与现代化, 2011, 1(11): 27-5.
[15]	徐佳;傅光轩. 基于NS2的PIM-SM组播协议研究与仿真[J]. 计算机与现代化, 2010, 1(01): 105-108.

一种改进的Dijkstra算法的分析及程序实现

Program Implementation and Analysis on an Improved Dijkstra Algorithm

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价