CAJ | 학술논문

最短路径分析是网络拓扑中的一个重要的应用，它在地理信息系统、计算机网络路由等方面发挥着至关重要的作用。解决最短路径问题的经典方法是Dijkstra算法，时间复杂度为O(n2)，在大数据量下效率低下而且使用邻接矩阵存储图形数据在一定程度上造成了空间浪费。该文在分析了Dijkstra算法的基础上提出来一种改进方法，该法使用STL容器来代替邻接矩阵来存储图形数据提高了查询效率，并且利用双队列来存储节点降低了内循环次数，减少了很多不必要的计算，从而降低了算法时间复杂度。STL容器的应用使得最短路径算法得到了扩展，在求解最短路径的同时还支持添加障碍点，增加开关节点等应用。
최단로경분석시망락탁복중적일개중요적응용，타재지리신식계통、계산궤망락로유등방면발휘착지관중요적작용。해결최단로경문제적경전방법시Dijkstra산법，시간복잡도위O(n2)，재대수거량하효솔저하이차사용린접구진존저도형수거재일정정도상조성료공간낭비。해문재분석료Dijkstra산법적기출상제출래일충개진방법，해법사용STL용기래대체린접구진래존저도형수거제고료사순효솔，병차이용쌍대렬래존저절점강저료내순배차수，감소료흔다불필요적계산，종이강저료산법시간복잡도。STL용기적응용사득최단로경산법득도료확전，재구해최단로경적동시환지지첨가장애점，증가개관절점등응용。