CAJ | 학술논문

最短路算法在交通,通信等领域有非常重要的应用,许多网络问题都可以归结为一个最短路问题.Dijkstra最短路算法是一个非常有效的算法,在计算网络中某一个顶点到其他各顶点的最短路时,如果引入Fibonacci堆,则Dijkstra算法运行所需要的加法及比较次数大致为O (m+nlogn),其中,m,n分别为网络的边数和顶点数.但由于在算法执行过程中,对Fibonacci堆的操作也有一定的代价.本文根据大型稀疏网络的特点,对Dijkstra最短路算法提出了一些非常简单的,但是非常有用的改进,并由此得到一个针对大型稀疏网络的Dijkstra最短路算法,该算法不需要构造Fibonacci堆,并且算法在运行时也只需要加法与比较,其所需要加法和比较的次数为O (m+nlog(n!)),其中D为网络中与顶点相关联边数的最大值.对于大型稀疏网络,如公路交通网络,D通常比较小,因此,所给算法对这类网络是非常有效的.
최단로산법재교통,통신등영역유비상중요적응용,허다망락문제도가이귀결위일개최단로문제.Dijkstra최단로산법시일개비상유효적산법,재계산망락중모일개정점도기타각정점적최단로시,여과인입Fibonacci퇴,칙Dijkstra산법운행소수요적가법급비교차수대치위O (m+nlogn),기중,m,n분별위망락적변수화정점수.단유우재산법집행과정중,대Fibonacci퇴적조작야유일정적대개.본문근거대형희소망락적특점,대Dijkstra최단로산법제출료일사비상간단적,단시비상유용적개진,병유차득도일개침대대형희소망락적Dijkstra최단로산법,해산법불수요구조Fibonacci퇴,병차산법재운행시야지수요가법여비교,기소수요가법화비교적차수위O (m+nlog(n!)),기중D위망락중여정점상관련변수적최대치.대우대형희소망락,여공로교통망락,D통상비교소,인차,소급산법대저류망락시비상유효적.