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