时间依赖网络中非FIFO弧的转化研究  

Study on the Conversion of Non-FIFO Arc in Time-dependent Networks

作　　者：余伟辉[1] 陈闳中[1] 

机构地区：[1]同济大学计算机科学与技术系,上海201804

出　　处：《小型微型计算机系统》2009年第1期156-158,共3页Journal of Chinese Computer Systems

基　　金：国家"八六三"项目(2007AA01Z136)资助

摘　　要：经典最短路算法不能有效地解决时间依赖网络的最短路问题.时间依赖网络中的非FIFO弧的存在是导致经典的最短路算法失效的原因.本文对非FIFO弧的权函数为非连续(存在有限个非连续点)或者离散情况下转化为FIFO弧进行了研究,在允许等待的前提条件下,提出了解决此类问题的方法.建立在经典Dijkstra算法基础上,本文提出了时间依赖网络最短路算法.Traditional algorithm can not effectively find out the shortest paths in time-dependent networks. The reason is that there are non-FIFO arcs in time-dependent networks. This paper studies on the method of converting the non-FIFO arcs into FIFO arcs in the condition of the function of this arcs is non-continuous （exist only limited non-continuous points） or discrete, then proposes the algorithm to solve this problem in the prerequisite of allowing wait. Based on the traditional Dijkstra algorithm, this paper develops the improved shortest-path in time-dependent network.

关 键 词：最短路 时间依赖网络 非FIFO弧 算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]