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

第7期 电 子 学 报 V01．34No．7 SD呵ICA 2006 2006年7月 ACTAELECTRON玉0A July 基于稳定分支的变权网络最优路径算法 林澜，闫春钢，辛肖刚，蒋昌俊 (同济大学计算机科学与技术系，上海201804) 摘要：有向网络的最短路问题在交通、通讯系统的最优传输路径中有重要应用．在通常的模型中，每条弧 的权是给定的．但在实际问题中，弧的权会发生变化，例如在交通拥堵时运行时间会变长．如果当权发生变化时， 要重新调用最短路算法，则浪费计算时间．本文提出最短路稳定性的概念，给出了关于最短路长度稳定、最优解稳 定与稳定分支的命题与理论证明，在此基础上给出一种新的变权网络最短路径算法，利用权发生变化前的信息， 减少计算量，提高计算效率．通过模拟实验验证了该算法的有效性． 关键词： 网络优化；最短路；变权；算法；稳定性 中图分类号：TP301 文献标识码： A Basedon Branch Path in Networks Stable Varying-Weight OptimalAlgorithm LIN Lan，YAN Xiao—gang，JIANGChang-jun Chun—gang，XIN and (DepartmentofComputerScienceTechnology，Tong]iUniversity，Shanghai201804，China) shortest ofdirectednetworksan rolein andcomma- Abstract：The importanttransportation pathalgorithm plays nicafion theclassical ofeacharcis it be inthe systems．In models，theweight givenbeforehand，butmayvaryingpracti- run in traffic is costtorunthe each cal instancethe timewouldincreasethe jaln．Ithigh Dijkstraalgorithm problems，for to the ofthe timewhen ofthe occur ina scalenetwork．Inorder large improveefficiency changesweightsfrequently the shortest inthe makeuseoftheinformationofthenetwor