计算机与现代化 ›› 2011, Vol. 1 ›› Issue (1): 36-3.doi: 10.3969/j.issn.1006-2475.2011.01.010
• 算法分析与设计 • 上一篇 下一篇
郝春梅
收稿日期:
修回日期:
出版日期:
发布日期:
HAO Chun-mei
Received:
Revised:
Online:
Published:
摘要:
Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法。本文通过对传统的Dijkstra算法进行分析,提出一种改进算法,经理论分析,对于顶点数较多而边数较少的有向稀疏图来说,在求最短路径时能够大大提高算法的运行效率。
关键词: 最短路径, Dijsktra算法, 改进算法
Abstract:
Dijkstra algorithm is an algorithm for solving singlesource shortestpaths 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: shortestpath, 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.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://www.c-a-m.org.cn/CN/10.3969/j.issn.1006-2475.2011.01.010
http://www.c-a-m.org.cn/CN/Y2011/V1/I1/36