Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length ARIEL ORDA AND RAPHAEL ROM Technion-Israel Institute of Technology, Haifa. Israel Abstract. In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting constraints are presented and the properties of the derived path are investigated. It is shown that if departure time from the source node is unrestricted, then a shortest path can be found that is simple and achieves a delay as short as the most unrestricted path. In the case of restricted transit, it is shown that there exist cases in which the minimum delay is finite, but the path that achieves it is infinite. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnu- merical Algorithms and Problems-computations on discrete structures; G.2.1 [Discrete Mathematics]: Graph Theory-graph algorithms, path and circuit problems General Terms: Algorithms, Network algorithms, Shortest paths Additional Key Words and Phrases: Functional complexity, time dependency, waiting times 1. Introduction Shortest-path algorithms have been the subject of extensive research for many years resulting in a large number of algorithms for various conditions and constraints [2]. The vast majority of these deal with fixed graphs, that is, fixed topology and fixed link weights. The advancement of computer networks and distributed processing has brought renewed interest in the subject with a new twist: time dependency. Several works have been published dealing with topological changes in which links may occasion- ally become unavailable (i.e., infinite weight) and others deal with quasi-static models, that is, link weights that change from time to time but remain constant in between these (infrequent) changes [6, 131. Time-dependent shortest-path problems have been studied in the case of discrete delay functions whose domain and range are the positive integers. Such problems were addressed both directly [ 1, 1 l] and indirectly in the context of maximal flow [7, 81. In this paper, we address the shortest-path problem without these restrictions, that is, we allow arbitrary functions for link delays. In this respect, this is the The research of the authors was supported by the Fobndation for Research in Electronics, Computers, and Communications, administered by the Israel Academy of Science and Humanities. Authors’ present addresses: A. Orda, Department of Electrical Engineering, Technion-Israel Institute of Technology, Haifa, Israel 32000; R. Rom, Sun Microsystems, Inc., MS14-49, 2550 Garcia Avenue, Mountain View, CA 94043. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1990 ACM 0004-541 l/90/0700-0607 $01.50 Journal of the Association for Computing Machinery, Vol. 37, No. 3, July 1990, pp. 607-625.608 A. ORDA AND R. ROM broadest generalization. Such a problem was briefly treated by Dreyfus [4] and Ling et al. [ 121, which address only limited cases. The most direct treatment to date was done by Halpern [lo] where arbitrary waiting times are also considered. In this latter work, an algorithm is proposed for various waiting constraints, but this algorithm cannot be bounded by network topology (i.e., the number of operations cannot be bounded by a function of the number of nodes or edges) nor are the properties of the resulting path investigated (e.g., whether it is a simple path). All the above works avoid the treatment of functions by addressing the problem for a single instance of time and not for time ranges. In this paper, we present algorithms for finding the shortest path and minimum delay for all instances of time and under various waiting constraints and investigate properties of the derived path. We show that if messages can be arbitrarily delayed at the source node, then a shortest path can be found that is simple and achieves a delay as short as the most unrestricted path, without having to wait en route. Our interpretation of time dependency of links is that of message traversal. For example, one interpretation might be the delay incurred by a message traversing the links. We note that time dependency may not be a continuous function. Consider a dial-up link between two nodes that is established and disestablished periodically. A message arriving while the link is established will suffer a relatively short delay, whereas a message arriving immediately after the link is disestablished will suffer a much greater delay. We also do not restrict ourselves to FIFO (first-in-first-out) links only, since in some potential cases the FIFO assumption is invalid. For example, consider a link composed of two physical communication channels one being faster than the other. If the policy of link management is to send a message over the first available channel, then a message sent over the slower one may arrive later than another message, sent later on the faster channel, meaning that messages arrive in a non- FIFO order. Our interest in the problem stems from related problems in computer commu- nication networks; hence, our reference to “messages.” Nonetheless, the results reported here hold for a general graph. In particular, some transportation networks may serve as good examples. One such example (following [ 121) is a traveler standing on a platform in a railway station wondering whether to take the local train stopping in front of him or