Optimal Path Algorithm in Varying-Weight Networks Based on Stable Branch
Jiang Changjun · Dianzi xuebao · 2006
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.