时间依赖有向无环网最小时间路径算法

摘要：

经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中弧权往往是动态的,即弧权依赖时间变化.本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现.该算法是一种改进的扩散法,克服了扩散法的一些显著缺点.文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算法的正确性。

关键词： 最小时间路径 时间依赖 有向无环网 路径算法 扩散法

作者: 余伟辉 陈闳中

作者单位: 同济大学电子与信息工程学院,上海,201804

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 42-45

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）