Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length

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.

https://doi.org/10.1145/79147.214078

Cite as:

@article{Orda_1990,
	doi = {10.1145/79147.214078},
	url = {https://doi.org/10.1145%2F79147.214078},
	year = 1990,
	month = {jul},
	publisher = {Association for Computing Machinery ({ACM})},
	volume = {37},
	number = {3},
	pages = {607--625},
	author = {Ariel Orda and Raphael Rom},
	title = {Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length},
	journal = {Journal of the {ACM}}
}