Determination of shortest path in a network with time-dependent edge-lengths1

Abstract

The solution of the shortest path problem in case of time-independent edge-lengths is due to FORD and FULKERSON [1,2]. By using the method of dynamic programming, BELLMAN [3] gave a procedure for the determination of the length of the shortest path. Following this principle COOKE and HALSEY [4] have a procedure for the determination of the length of the shortest path in case of time-dependent edge-lengths. This procedure, however, gives only the length of the path, not the path itself. We shall demonstrate in this paper that the method of FORD and FULKERSON leads itself too to solution of the problem, morcover it gives also the shortest path.