Ariel Orda
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.
- 1 COOKE, K. L., AND HALSEY, E. The shortest route through a network with time dependent internodal transit times. J. Math. Anal. Appl. 14 (1966), 493-498.Google Scholar
- 2 DEO, N., AND PANG, C.Y. Shortest path algorithms: Taxonomy and annotation. Networks 14 (1984), 275-323.Google Scholar
- 3 DIJKSTRA, E.W. A note on two problems in connection with graphs. Num. Anal. 1 (Oct. 1959), 269-271.Google Scholar
- 4 DREYFUS, S.E. An appraisal of some shortest path algorithms. Oper. Res. 17 (1969), 395-412.Google Scholar
- 5 EVEN, S. Graph Algorithms. Computer Science Press, New York, 1979. Google Scholar
- 6 EVEN, S., AND GAZIT, H. Updating distances in dynamic graphs. Meth. Oper. Res. 49 (May 1985), 371-387.Google Scholar
- 7 FORD, L. R., JR., AND FULKERSON, D.R. Constructing maximal dynamic flows from static flows. Oper. Res. 6 (1958), 419-433.Google Scholar
- 8 FORD, L. R., JR., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.Google Scholar
- 9 GERLA, M., AND KLEINROCK, L. Flow control: A comparative survey. IEEE Trans. Commun. COM-28, 4 (Apr. 1980), 553-574.Google Scholar
- 10 HALPERN, J. The shortest route with time dependent length of edges and limited delay possibilities in nodes. Z. Oper. Res. 21 (1977), 117-124.Google Scholar
- 11 KLAFSZKY, E. Determination of shortest path in a network with time-dependent edge-lengths. Math. Oper. Stat. 3 (1972), 255-257.Google Scholar
- 12 LING, S. T., FURUNO, K., AND TEZUKA, Y. Optimal path in networks with time-varying traverse time and expenses branches. Tech. Rep. of Osaka University, Japan, 1972.Google Scholar
- 13 McQUILLAN, J. M., RICHER, I., AND ROSEN, E.C. The new routing algorithm for the ARPANET. IEEE Trans. Commun. COM-28, 5 (May 1980), 71 I-719.Google Scholar
- 14 ORDA, A., AND ROM, R. Distributed shortest-path protocols for time-dependent networks. In Proceedings oflCCC 88 (Tel Aviv, Israel, Nov. 1988), pp. 439-445.Google Scholar
- 15 ORDA, A., AND ROM, R. Minimum weight paths in time-dependent networks. EE Publication No. 710. Faculty of Electrical Engineering, Technion, Haifa, Israel, Mar. 1989.Google Scholar
- 16 SEGALL, A. Distributed network protocols. IEEE Trans. on Inf. Theory(Jan. 1983), 23-34.Google Scholar
Index Terms
- Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
Recommendations
Delay-Constrained Minimum Shortest Path Trees and Related Problems
Combinatorial Optimization and ApplicationsAbstractMotivated by applications in communication networks of the diameter-constrained minimum spanning tree problem, we consider the delay-constrained minimum shortest path tree (DcMSPT) problem. Specifically, given a weighted graph and a ...
Delay-constrained minimum shortest path trees and related problems
AbstractMotivated by some applications in communication networks of the diameter-constrained minimum spanning tree (Diamc-MST) problem, we address the delay-constrained minimum shortest path tree (Delayc-MSPT) problem, which is a variation of ...
Highlights- We study the delay-constrained minimum shortest path tree problem and related problems.
Comments