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

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

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

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.