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

扫码查看

原文链接

国家科技期刊平台
NETL
NSTL
万方数据
维普

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

外文标题：Program Implementation and Analysis on an Improved Dijkstra Algorithm

外文摘要：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.

作者：

郝春梅

展开 >

作者单位：

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

关键词：

最短路径 Dijsktra算法改进算法

出版年：

2011

DOI：

10.3969/j.issn.1006-2475.2011.01.010

计算机与现代化