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

Abstract:

Shortest path problems lie at the heart of network flows, which arise frequently in both engineering and scientific applications. In the classical net  work 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. T  his 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 thi s 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.

Key words: minimum-tirae path, time-dependant, directed acyclic network, flooding, algorithm