摘要
主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。
In this paper,the shortest path problem,which has dynamic characteristic in the network combinatorial optimization field,is studied,and descriptions of dynamic shortest path problems about time and cost on discrete time model are provided.By introducing the concept of time-expanded graph,the dynamic network problem can be transformed into corresponding static shortest path problem.Then the complexities of two dynamic shortest path problems are discussed and the arithmetics given.
出处
《东莞理工学院学报》
2009年第5期31-34,共4页
Journal of Dongguan University of Technology
关键词
动态最短路
时间扩张图
最小时间路径
最小费用路径
dynamic shortest path
time-expanded graph
the minimum time path
the minimum cost path
