基于稳定分支的变权网络最优路径算法

有向网络的最短路问题在交通、通讯系统的最优传输路径中有重要应用.在通常的模型中,每条弧的权是给定的.但在实际问题中,弧的权会发生变化,例如在交通拥堵时运行时间会变长.如果当权发生变化时,要重新调用最短路算法,则浪费计算时间.本文提出最短路稳定性的概念,给出了关于最短路长度稳定、最优解稳定与稳定分支的命题与理论证明,在此基础上给出一种新的变权网络最短路径算法,利用权发生变化前的信息,减少计算量,提高计算效率.通过模拟实验验证了该算法的有效性.

Optimal Path Algorithm in Varying-Weight Networks Based on Stable Branch

The shortest path algorithm of directed networks plays an important role in transportation and communication systems. In the classical models, the weight of each arc is given beforehand, but it may be varying in the practical problems ,for instance the run time would increase in the traffic jam. It is high cost to run the Dijkstra algorithm each time when changes of the weights occur frequently in a large scale network. In order to improve the efficiency of the shortest path computation in the varying-weight networks, we make use of the information of the network before the weights altered. The concept of the stability of shortest paths is presented, and a new stable brand-based algorithm is proposed. Experimental simulation shows that the new algorithm improves the efficiency of the varying-weight optimal path computation significantly.