随机时间依赖网络的K期望最短路径

摘要

首先给出了随机时间依赖网络模型、K期望最短路径问题的形式化描述,并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数、路径期望耗费的计算方法;然后,基于随机一致性假设和随机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性;最后,给出了公交网络的应用实例和实验结果.