CAJ | 학술논문

针对传统Dijkstra算法运行效率的问题，提出了一种基于传统Dijkstra并行线程的算法，该算法动态地将交通网络进行子网分割。通过实验测试了不同网络节点数量和弧段数量下传统Dijkstra算法和本文算法运行时间，实验结果表明本文算法能够缩减网络节点搜索空间，降低算法的时间复杂度，提高算法的运行效率。
침대전통Dijkstra산법운행효솔적문제，제출료일충기우전통Dijkstra병행선정적산법，해산법동태지장교통망락진행자망분할。통과실험측시료불동망락절점수량화호단수량하전통Dijkstra산법화본문산법운행시간，실험결과표명본문산법능구축감망락절점수색공간，강저산법적시간복잡도，제고산법적운행효솔。
Aiming at the problem of operating efficiency of traditional Dijkstra algorithm, the paper comes up with one algorithm of parallel thread based on traditional Dijkstra.The algorithm divises traffic network into subnets dynamically.Through experiment, the operating time of traditional Dijkstra algorithm is tested under different number of network junctions and arcs.The experiment has demonstrated that the algorithm can lower searching space of network junctions, reduce Dijkstra time complexity and improve Dijkstra operating efficiency.