摘要： 动态(时间依赖的)容量网络与传统静态网络相比更具现实意义，在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上，研究具有实际背景的动态容量网络的最小最大时间流问题，给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例，其时间复杂度为O(mMv)。

关键词: 动态容量网络, 时间依赖网络, 最小最大时间流, 多项式算法

Abstract: The capacitated dynamic(time-dependent) networks are more realistic than the classical static networks, and are applicated to a wide range of fields including transportation, logistics and telecommunication network systems. Based on the shortest path algorithm in time-dependent networks, this paper studies the min max-time flow problem in capacitated dynamic networks with real background, and presents an algorithm to solve this problem. The running time complexity of this algorithm is in O(mMn).

Key words: capacitated dynamic networks, time-dependent networks, min max-time flow, polynomial algorithm

中图分类号: 

• TP393