时间依赖的网络中最小时间路径算法

摘要

时间依赖的网络与传统网络模型相比更具有现实意义,具有广泛的应用领域.交通网络和通信网络可以抽象为时间依赖的网络模型.当模型中弧的长度是时间依赖的变量,最短路径问题的求解变得非常困难,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的,因此给出限制性条件使得传统最短路径算法是有效的.该文从最短路径算法的理论基础入手,从理论上证明了传统最短路径算法,如Dijkstra算法和标号设置算法,在时间依赖的网络上不能有效地求解最短路径问题;并且,在没有任何限制性条件下,给出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件和SPTDN算法,从理论上证明了SPTDN算法的正确性.算法的实验结果是正确的.最后给出了时间依赖的网络应用实例.