CAJ | 학술논문

有向网络中，最短路径的计算在交通、通信等实际问题中有着重要的应用。通过对现有动态最短路径算法的深入研究，提出一种处理网络拓扑变化的全动态最短路径算法（Increase or Decrease of Edge Weight for Shortest Path Tree，IDEWSPT）。该算法利用初始最短路径树（Shortest Path Tree SPT）的信息，建立一个SPT的更新队列，当网络拓扑发生变化时，将更新范围局限在受拓扑变化影响的节点中，从而达到控制冗余更新的目的。算法复杂度分析和仿真结果显示，IDEWSPT算法具更高的时间效率。
유향망락중，최단로경적계산재교통、통신등실제문제중유착중요적응용。통과대현유동태최단로경산법적심입연구，제출일충처리망락탁복변화적전동태최단로경산법（Increase or Decrease of Edge Weight for Shortest Path Tree，IDEWSPT）。해산법이용초시최단로경수（Shortest Path Tree SPT）적신식，건립일개SPT적경신대렬，당망락탁복발생변화시，장경신범위국한재수탁복변화영향적절점중，종이체도공제용여경신적목적。산법복잡도분석화방진결과현시，IDEWSPT산법구경고적시간효솔。
The shortest path problem of directed network is significant in the transportation and communi-cation systems. Based on the research on the present dynamic SPT algorithm, we proposed a new complete dynamic SPT algorithm for the network topology changing. This algorithm establishes an SPT update queue and pays attention only to the changes of nodes and edges by taking use of the useful information provided by the existing SPT, which can reduce redundant update. The complexity analysis of algorithm and simulation results shows that IDEWSPT has higher e?ciency.