文献类型：期刊文章

作　　者：王树西[1] 李安渝[2]

机构地区：[1]对外经济贸易大学信息学院,北京100029 [2]对外经济贸易大学电子商务研究所,北京100029

出　　处：《计算机科学》

基　　金：对外经济贸易大学信息学院基金;对外经贸大学:<信息系统建设与实施>案例研究(X12511);对外经贸大学:商务信息系统应用(X10017);对外经济贸易大学中央高校基本科研业务费专项资金(13YBLG02)资助

年　　份：2014

卷　　号：41

期　　号：6

起止页码：217-224

语　　种：中文

收录情况：BDHX、BDHX2011、CSA、CSCD、CSCD2013_2014、IC、JST、RCCSE、UPD、ZGKJHX、核心刊

摘　　要：Dijkstra算法是图论中求取最短路径的经典算法。列举并分析了Dijkstra算法及其伪码,为了深刻理解Dijkstra算法,列举了几种错误观点并加以纠正。分析发现,根据Dijkstra算法,最短路径上的某个顶点的前面,可能有多个邻接点;从开始点到某个顶点之间,可能存在多条权重相同的最短路径。对于上述多邻接点问题与多条最短路径问题,Dijkstra算法并没有涉及。分析了多邻接点问题与多条最短路径问题的成因,提出解决方案,对Dijkstra算法进行了改进,给出了改进之后的算法与伪码,分析了算法的时间复杂度,并用c语言编码实现。实验结果表明,改进之后的Dijkstra算法可以有效解决多邻接点问题与多条最短路径问题。

关 键 词：DIJKSTRA算法 多邻接点  多条最短路径  时间复杂度

分 类 号：TP392]