计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
6期
217-224
,共8页
Dijkstra算法%多邻接点%多条最短路径%时间复杂度
Dijkstra算法%多鄰接點%多條最短路徑%時間複雜度
Dijkstra산법%다린접점%다조최단로경%시간복잡도
Dijkstra algorithm%Multiple pre-adjacent vertexes%Multiple shortest paths%Time complexity
Dijkstra算法是图论中求取最短路径的经典算法.列举并分析了Dijkstra算法及其伪码,为了深刻理解Dijkstra算法,列举了几种错误观点并加以纠正.分析发现,根据Dijkstra算法,最短路径上的某个顶点的前面,可能有多个邻接点;从开始点到某个顶点之间,可能存在多条权重相同的最短路径.对于上述多邻接点问题与多条最短路径问题,Dijkstra算法并没有涉及.分析了多邻接点问题与多条最短路径问题的成因,提出解决方案,对Dijkstra算法进行了改进,给出了改进之后的算法与伪码,分析了算法的时间复杂度,并用c语言编码实现.实验结果表明,改进之后的Dijkstra算法可以有效解决多邻接点问题与多条最短路径问题.
Dijkstra算法是圖論中求取最短路徑的經典算法.列舉併分析瞭Dijkstra算法及其偽碼,為瞭深刻理解Dijkstra算法,列舉瞭幾種錯誤觀點併加以糾正.分析髮現,根據Dijkstra算法,最短路徑上的某箇頂點的前麵,可能有多箇鄰接點;從開始點到某箇頂點之間,可能存在多條權重相同的最短路徑.對于上述多鄰接點問題與多條最短路徑問題,Dijkstra算法併沒有涉及.分析瞭多鄰接點問題與多條最短路徑問題的成因,提齣解決方案,對Dijkstra算法進行瞭改進,給齣瞭改進之後的算法與偽碼,分析瞭算法的時間複雜度,併用c語言編碼實現.實驗結果錶明,改進之後的Dijkstra算法可以有效解決多鄰接點問題與多條最短路徑問題.
Dijkstra산법시도론중구취최단로경적경전산법.열거병분석료Dijkstra산법급기위마,위료심각리해Dijkstra산법,열거료궤충착오관점병가이규정.분석발현,근거Dijkstra산법,최단로경상적모개정점적전면,가능유다개린접점;종개시점도모개정점지간,가능존재다조권중상동적최단로경.대우상술다린접점문제여다조최단로경문제,Dijkstra산법병몰유섭급.분석료다린접점문제여다조최단로경문제적성인,제출해결방안,대Dijkstra산법진행료개진,급출료개진지후적산법여위마,분석료산법적시간복잡도,병용c어언편마실현.실험결과표명,개진지후적Dijkstra산법가이유효해결다린접점문제여다조최단로경문제.
