Nondecreasing paths in a weighted graph or: how to optimally read a train schedule

ABSTRACT

A travel booking office has timetables giving arrival and departure times for all scheduled trains, including their origins and destinations. A customer presents a starting city and demands a route with perhaps several train connections taking him to his destination as early as possible. The booking office must find the best route for its customers. This problem was first considered in the theory of algorithms by George Minty [14], who reduced it to a problem on directed edge-weighted graphs: find a path from a given source to a given target such that the consecutive weights on the path are nondecreasing and the last weight on the path is minimized. Minty gave the first algorithm for the single source version of the problem, in which one finds minimum last weight nondecreasing paths from the source to every other vertex. In this paper we give the first linear time algorithm for this problem. We also define an all pairs version for the problem and give a strongly polynomial truly subcubic algorithm for it.

REFERENCES

• 1: R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16(1), 87--90, 1958.
• 2: G. Brodal and R. Jacob. Time-dependent networks as models to achieve fast exact time-table queries. In Proceedings of ATMOS Workshop 2003, Electronic Notes in Theoretical Computer Science 92, 2004.
• 3: Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250877]
• 4: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 5: E. W. Dijkstra. A note on two problems in connection with graphs. Numer. Math., 269--271, 1959.
• 6: L. R. Ford. Network flow theory. Technical Report Paper P-923, The Rand Corporation, Santa Monica, 1956.
• 7: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 8: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 9: Zvi Galil , Oded Margalit, All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, v.54 n.2, p.243-254, April 1997 [doi>10.1006/jcss.1997.1385]
• 10: Andrew V. Goldberg, Scaling algorithms for the shortest paths problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.222-231, January 25-27, 1993, Austin, Texas, United States
• 11: Yijie Han, An O(n³ (loglogn/logn)^5/4) time algorithm for all pairs shortest paths, Proceedings of the 14th conference on Annual European Symposium, p.411-417, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_38]
• 12: M. Kowaluk and A. Lingas. LCA queries in directed acyclic graphs. In Proc. of ICALP, Springer-Verlag LNCS 3580:241--248, 2005.
• 13: Jiří Matoušek, Computing dominances inEn (short communication), Information Processing Letters, v.38 n.5, p.277-278, June 14, 1991 [doi>10.1016/0020-0190(91)90071-O]
• 14: G. J. Minty. A Variant on the Shortest-Route Problem, Operations Research, 6(6):882--883, 1958.
• 15: E. F. Moore. The shortest path through a maze. In Proceedings of an International Symposium on the Theory of Switching, 285--292, 2--5 April 1957, Part II, 1959.
• 16: Evangelia Pyrga , Frank Schulz , Dorothea Wagner , Christos Zaroliagis, Efficient models for timetable information in public transportation systems, Journal of Experimental Algorithmics (JEA), 12, June 2008
• 17: Frank Schulz , Dorothea Wagner , Christos D. Zaroliagis, Using Multi-level Graphs for Timetable Information in Railway Systems, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.43-59, January 04-05, 2002
• 18: Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078]
• 19: Asaf Shapira , Raphael Yuster , Uri Zwick, All-pairs bottleneck paths in vertex weighted graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.978-985, January 07-09, 2007, New Orleans, Louisiana
• 20: Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999
• 21: R. E. Tarjan, Private communication.
• 22: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 23: Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132550]
• 24: Virginia Vassilevska , Ryan Williams , Raphael Yuster, All-pairs bottleneck paths for general graphs in truly sub-cubic time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250876]
• 25: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory