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

A Minimum-Time Path Algorithm in Time-Dependent Directed Acyclic Networks

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

机构地区：[1]同济大学电子与信息工程学院,上海201804

出　　处：《计算机工程与科学》2008年第11期42-45,共4页Computer Engineering & Science

基　　金：国家863计划资助项目(2007AA01Z136)

摘　　要：经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中弧权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算法的正确性。Shortest path problems lie at the heart of network flows, which arise frequently in both engineering and scientific applications. In the classical network models,the weight of each arc is invariant and usually given beforehand,but it may be varying in the practical problems which are time-dependent. This paper proposes a reusable minimum-time path algorithm for the solution to a special time-dependent network, directed acyclie network. This algorithm obtains reusable tree by the use of the improved Breadth-First Search in limited time,and makes the hash index of this reusable tree to improve the com- plexity of reuse. We can get the shortest path from the leaves of a tree,which contain the time spent on traveling from the root to the leaf. Then this paper proves the correctness of the theory. In the end,this paper cites an example which can not be effectively resolved by the classical algorithms to prove the correctness of the theory.

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

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