首页 | 本学科首页   官方微博 | 高级检索  
     

时间依赖有向无环网最小时间路径算法
引用本文:余伟辉,陈闳中. 时间依赖有向无环网最小时间路径算法[J]. 计算机工程与科学, 2008, 30(11): 42-45
作者姓名:余伟辉  陈闳中
作者单位:同济大学电子与信息工程学院,上海,201804;同济大学电子与信息工程学院,上海,201804
基金项目:国家高技术研究发展计划(863计划)
摘    要:经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中孤权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算算:法的正确性。

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

A Minimum-Time Path Algorithm in Time-Dependent Directed Acyclic Networks
YU Wei-hui,CHEN Hong-zhong. A Minimum-Time Path Algorithm in Time-Dependent Directed Acyclic Networks[J]. Computer Engineering & Science, 2008, 30(11): 42-45
Authors:YU Wei-hui  CHEN Hong-zhong
Abstract: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 acyclic 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 complexity 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.
Keywords:minimum-time path  time-dependant  directed acyclic network  flooding  algorithm
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程与科学》浏览原始摘要信息
点击此处可从《计算机工程与科学》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号