随机时间依赖网络的K期望寿命最短路径算法研究

摘要

在交通网络和数据网络中,网络特征(如弧的权值、结点耗费等)既具有随机性又具有时间依赖性,这样的网络称之为随机时间依赖网络,简记为STD网络.在实践中,STD网络模型比传统网络模型具有更广泛的应用.由于随机性和时间依赖性引入到网络模型中,使得最短路径问题变得复杂化和多样化,传统的最短路径算法已不再适应这样复杂的网络环境,这就迫使我们寻求新的解决方法.本文解决的问题是,STD网络中,在任意时刻从单源点出发到达单目的地的预先K期望最短路径问题.我们将可靠性理论应用于该问题的求解中,推导出新优势判别法,使得传统判别法中的参数由二维降到一维,减小了路径间不可比较的可能性,既节省了存储空间又加快了搜索速度.然后,设计并实现了求解该问题的K_RELSP算法,并通过试验验证了该算法具有很高的运行效率.