{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T15:47:13Z","timestamp":1773676033135,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2005,12,31]]},"abstract":"<jats:p>A fundamental approach in finding efficiently best routes or optimal itineraries in traffic information systems is to reduce the search space (part of graph visited) of the most commonly used shortest path routine (Dijkstra's algorithm) on a suitably defined graph. We investigate reduction of the search space while simultaneously retaining data structures, created during a preprocessing phase, of size linear (i.e., optimal) to the size of the graph. We show that the search space of Dijkstra's algorithm can be significantly reduced by extracting geometric information from a given layout of the graph and by encapsulating precomputed shortest-path information in resulted geometric objects (containers). We present an extensive experimental study comparing the impact of different types of geometric containers using test data from real-world traffic networks. We also present new algorithms as well as an empirical study for the dynamic case of this problem, where edge weights are subject to change and the geometric containers have to be updated and show that our new methods are two to three times faster than recomputing everything from scratch. Finally, in an appendix, we discuss the software framework that we developed to realize the implementations of all of our variants of Dijkstra's algorithm. Such a framework is not trivial to achieve as our goal was to maintain a common code base that is, at the same time, small, efficient, and flexible, as we wanted to enhance and combine several variants in any possible way.<\/jats:p>","DOI":"10.1145\/1064546.1103378","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":50,"title":["Geometric containers for efficient shortest-path computation"],"prefix":"10.1145","volume":"10","author":[{"given":"Dorothea","family":"Wagner","sequence":"first","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"University of Patras, Patras, Greece"}]}],"member":"320","published-online":{"date-parts":[[2005,12,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Modern C&plus;&plus","author":"Alexandrescu A.","unstructured":"Alexandrescu , A. 2001. Modern C&plus;&plus ; design: generic programming and design patterns applied. Addison-Wesley , Reading, MA .]] Alexandrescu, A. 2001. Modern C&plus;&plus; design: generic programming and design patterns applied. Addison-Wesley, Reading, MA.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90036-X"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_1_4_1","volume-title":"Proc. 10th European Symposium on Algorithms (ESA","volume":"2461","author":"Barrett C.","year":"2002","unstructured":"Barrett , C. , Bisset , K. , Jacob , R. , Konjevod , G. , and Marathe , M . 2002. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router . In Proc. 10th European Symposium on Algorithms (ESA 2002 ), R. M\u00f6hring and R. Raman, Eds. LNCS , vol. 2461 . Springer, New York. 126--138.]] Barrett, C., Bisset, K., Jacob, R., Konjevod, G., and Marathe, M. 2002. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. In Proc. 10th European Symposium on Algorithms (ESA 2002), R. M\u00f6hring and R. Raman, Eds. LNCS, vol. 2461. Springer, New York. 126--138.]]"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/97945.97982"},{"key":"e_1_2_1_6_1","volume-title":"Eds. LNCS","volume":"2265","author":"Brandes U.","unstructured":"Brandes , U. , Eiglsperger , M. , Herman , I. , Himsolt , M. , and Scott , M . 2001. GraphML progress report. P. Mutzel, M. J\u00fcnger, and S. Leipert , Eds. LNCS , vol. 2265 . Springer, New York. 501--512.]] Brandes, U., Eiglsperger, M., Herman, I., Himsolt, M., and Scott, M. 2001. GraphML progress report. P. Mutzel, M. J\u00fcnger, and S. Leipert, Eds. LNCS, vol. 2265. Springer, New York. 501--512.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780567"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_9_1","volume-title":"Proc. 1st Workshop on C&plus;&plus; Template Programming","author":"Eisenecker U. W.","unstructured":"Eisenecker , U. W. , Blinn , F. , and Czarnecki , K . 2000. A solution to the constructor-problem of mixin-based programming in C&plus;&plus; . In Proc. 1st Workshop on C&plus;&plus; Template Programming . Erfurt, Germany.]] Eisenecker, U. W., Blinn, F., and Czarnecki, K. 2000. A solution to the constructor-problem of mixin-based programming in C&plus;&plus;. In Proc. 1st Workshop on C&plus;&plus; Template Programming. Erfurt, Germany.]]"},{"key":"e_1_2_1_10_1","first-page":"371","article-title":"Updating distances in dynamic graphs","volume":"49","author":"Even S.","year":"1985","unstructured":"Even , S. and Gazit , H. 1985 . Updating distances in dynamic graphs . Methods of Operations Research 49 , 371 -- 387 .]] Even, S. and Gazit, H. 1985. Updating distances in dynamic graphs. Methods of Operations Research 49, 371--387.]]","journal-title":"Methods of Operations Research"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11%3C1167::AID-SPE337%3E3.0.CO;2-B"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009224"},{"key":"e_1_2_1_14_1","volume-title":"Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96)","author":"Frigioni D.","unstructured":"Frigioni , D. , Marchetti-Spaccamela , A. , and Nanni , U . 1996. Fully dynamic output bounded single source shortest path problem . In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96) . 212--221.]] Frigioni, D., Marchetti-Spaccamela, A., and Nanni, U. 1996. Fully dynamic output bounded single source shortest path problem. In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96). 212--221.]]"},{"key":"e_1_2_1_15_1","volume-title":"Design Patterns: Elements od Reusable Object-Oriented Software","author":"Gamma E.","year":"1995","unstructured":"Gamma , E. , Helm , R. , Johnson , R. , and Vlissides , J . 1995 . Design Patterns: Elements od Reusable Object-Oriented Software . Addison-Wesley Professional Computing Series. Addison-Wesley , Reading, MA.]] Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns: Elements od Reusable Object-Oriented Software. Addison-Wesley Professional Computing Series. Addison-Wesley, Reading, MA.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_43"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24838-5_20"},{"key":"e_1_2_1_18_1","volume-title":"Proc. 2nd Workshop on Algorithm Engineering (WAE'98)","author":"Jacob R.","unstructured":"Jacob , R. , Marathe , M. , and Nagel , K . 1998. A computational study of routing algorithms for realistic transportation networks . In Proc. 2nd Workshop on Algorithm Engineering (WAE'98) , K. Mehlhorn, Ed. 167--178. Available at: http:\/\/www.mpi-sb.mpg.de\/~wae98\/PROCEEDINGS\/.]] Jacob, R., Marathe, M., and Nagel, K. 1998. A computational study of routing algorithms for realistic transportation networks. In Proc. 2nd Workshop on Algorithm Engineering (WAE'98), K. Mehlhorn, Ed. 167--178. Available at: http:\/\/www.mpi-sb.mpg.de\/~wae98\/PROCEEDINGS\/.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_2_1_22_1","unstructured":"Mehlhorn K. and N\u00e4her S. 1999. LEDA A platform for Combinatorial and Geometric Computing. Cambridge University Press Cambridge.]]   Mehlhorn K. and N\u00e4her S. 1999. LEDA A platform for Combinatorial and Geometric Computing. Cambridge University Press Cambridge.]]"},{"key":"e_1_2_1_23_1","volume-title":"Proc. Symposium on Discrete Algorithms. 797--806","author":"Meyer U.","year":"2001","unstructured":"Meyer , U. 2001 . Single-source shortest-paths on arbitrary directed graphs in linear average-case time . In Proc. Symposium on Discrete Algorithms. 797--806 .]] Meyer, U. 2001. Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In Proc. Symposium on Discrete Algorithms. 797--806.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)E0349-G"},{"key":"e_1_2_1_25_1","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX'02)","volume":"2409","author":"Pettie S.","unstructured":"Pettie , S. , Ramachandran , V. , and Sridhar , S . 2002. Experimental evaluation of a new shortest path algorithm . In Proc. Algorithm Engineering and Experiments (ALENEX'02) . LNCS, vol. 2409 . Springer, New York. 126--142.]] Pettie, S., Ramachandran, V., and Sridhar, S. 2002. Experimental evaluation of a new shortest path algorithm. In Proc. Algorithm Engineering and Experiments (ALENEX'02). LNCS, vol. 2409. Springer, New York. 126--142.]]"},{"key":"e_1_2_1_26_1","volume-title":"Proc. 6th Annual Machine Intelligence Workshop, B. Meltzer and D. Michie, Eds. Machine Intelligence","volume":"6","author":"Pohl I.","year":"1971","unstructured":"Pohl , I. 1971 . Bi-directional search . In Proc. 6th Annual Machine Intelligence Workshop, B. Meltzer and D. Michie, Eds. Machine Intelligence , vol. 6 . Edinburgh University Press, London, 137--140.]] Pohl, I. 1971. Bi-directional search. In Proc. 6th Annual Machine Intelligence Workshop, B. Meltzer and D. Michie, Eds. Machine Intelligence, vol. 6. Edinburgh University Press, London, 137--140.]]"},{"key":"e_1_2_1_27_1","volume-title":"Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA '97)","author":"Preuss T.","unstructured":"Preuss , T. and Syrbe , J . -H. 1997. An integrated traffic information system . In Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA '97) .]] Preuss, T. and Syrbe, J.-H. 1997. An integrated traffic information system. In Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA '97).]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/18858.18885"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_32_1","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX'02)","volume":"2409","author":"Schulz F.","unstructured":"Schulz , F. , Wagner , D. , and Zaroliagis , C . 2002. Using multi-level graphs for timetable information . In Proc. Algorithm Engineering and Experiments (ALENEX'02) . LNCS, vol. 2409 . Springer, New York. 43--59.]] Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information. In Proc. Algorithm Engineering and Experiments (ALENEX'02). LNCS, vol. 2409. Springer, New York. 43--59.]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220338"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840435"},{"key":"e_1_2_1_35_1","volume-title":"Proc. Symposium on Large Spatial Databases. 94--111","author":"Shekhar S.","unstructured":"Shekhar , S. , Fetterer , A. , and Goyal , B . 1997. Materialization trade-offs in hierarchical shortest path algorithms . In Proc. Symposium on Large Spatial Databases. 94--111 .]] Shekhar, S., Fetterer, A., and Goyal, B. 1997. Materialization trade-offs in hierarchical shortest path algorithms. In Proc. Symposium on Large Spatial Databases. 94--111.]]"},{"key":"e_1_2_1_36_1","volume-title":"Proc. 9th IEEE Int. Conf. Data Eng. 31--39","author":"Shekhar S.","unstructured":"Shekhar , S. , Kohli , A. , and Coyle , M . 1993. Path computation algorithms for advanced traveler information system (ATIS) . In Proc. 9th IEEE Int. Conf. Data Eng. 31--39 .]] Shekhar, S., Kohli, A., and Coyle, M. 1993. Path computation algorithms for advanced traveler information system (ATIS). In Proc. 9th IEEE Int. Conf. Data Eng. 31--39.]]"},{"key":"e_1_2_1_37_1","unstructured":"Siek J. Lee L.-Q. and Lumsdaine A. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Reading MA.]]   Siek J. Lee L.-Q. and Lumsdaine A. 2002. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Reading MA.]]"},{"key":"e_1_2_1_38_1","volume-title":"An aspect-oriented extension to the C&plus;&plus","author":"Spinczyk O.","year":"2002","unstructured":"Spinczyk , O. , Gal , A. , and Schroder-Preikschat , W. 2002. Aspect C &plus;&plus; : An aspect-oriented extension to the C&plus;&plus ; programming language. In Proc. 40th International Conference on Technology of Object-Oriented Languages and Systems (TOOLS Pacific 2002 ), J. Noble and J. Potter, Eds. Conferences in Research and Practice in Information Technology, vol. 10 . ACS, Sydney, Australia . 53--60.]] Spinczyk, O., Gal, A., and Schroder-Preikschat, W. 2002. AspectC&plus;&plus;: An aspect-oriented extension to the C&plus;&plus; programming language. In Proc. 40th International Conference on Technology of Object-Oriented Languages and Systems (TOOLS Pacific 2002), J. Noble and J. Potter, Eds. Conferences in Research and Practice in Information Technology, vol. 10. ACS, Sydney, Australia. 53--60.]]"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796356"},{"key":"e_1_2_1_40_1","volume-title":"Proc. IEEE Mediteranian Electrotechnical Conference (MELECON","author":"Toussaint G.","year":"1983","unstructured":"Toussaint , G. 1983 . Solving geometric problems with the rotating calipers . In Proc. IEEE Mediteranian Electrotechnical Conference (MELECON 1983), E. N. Protonotarios, Ed. IEEE, New York. A10.02\/1-4.]] Toussaint, G. 1983. Solving geometric problems with the rotating calipers. In Proc. IEEE Mediteranian Electrotechnical Conference (MELECON 1983), E. N. Protonotarios, Ed. IEEE, New York. A10.02\/1-4.]]"},{"key":"e_1_2_1_41_1","volume-title":"Proc. 11th European Symposium on Algorithms (ESA","volume":"2832","author":"Wagner D.","year":"2003","unstructured":"Wagner , D. and Willhalm , T . 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs . In Proc. 11th European Symposium on Algorithms (ESA 2003 ), G. D. Battista and U. Zwick, Eds. LNCS , vol. 2832 . Springer, New York. 776--787.]] Wagner, D. and Willhalm, T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proc. 11th European Symposium on Algorithms (ESA 2003), G. D. Battista and U. Zwick, Eds. LNCS, vol. 2832. Springer, New York. 776--787.]]"},{"key":"e_1_2_1_42_1","volume-title":"Proc. 7th Workshop Algorithm Engineering and Experiments (ALENEX'05)","author":"Wagner D.","unstructured":"Wagner , D. and Willhalm , T . 2005. Drawing graphs to speed up shortest-path computations . In Proc. 7th Workshop Algorithm Engineering and Experiments (ALENEX'05) . SIAM. To appear.]] Wagner, D. and Willhalm, T. 2005. Drawing graphs to speed up shortest-path computations. In Proc. 7th Workshop Algorithm Engineering and Experiments (ALENEX'05). SIAM. To appear.]]"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2003.12.023"},{"key":"e_1_2_1_44_1","volume-title":"New Results and New Trends in Computer Science","author":"Welzl E.","unstructured":"Welzl , E. 1991. Smallest enclosing disks (balls and ellipsoids) . In New Results and New Trends in Computer Science , H. Maurer, Ed. LNCS, vol. 555 . Springer , New York .]] Welzl, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, H. Maurer, Ed. LNCS, vol. 555. Springer, New York.]]"},{"key":"e_1_2_1_45_1","volume-title":"Fundamentals of modern statistical methods: substantially improving power and accuracy","author":"Wilcox R. R.","unstructured":"Wilcox , R. R. 2001. Fundamentals of modern statistical methods: substantially improving power and accuracy . Springer , New York .]] Wilcox, R. R. 2001. Fundamentals of modern statistical methods: substantially improving power and accuracy. Springer, New York.]]"},{"key":"e_1_2_1_46_1","volume-title":"Implementations and experimental studies of dynamic graph algorithms","author":"Zaroliagis C.","unstructured":"Zaroliagis , C. 2002. Implementations and experimental studies of dynamic graph algorithms . In Experimental Algorithmics, R. Fleischer, B. Moret, and E. M. Schmidt, Eds. LNCS, vol. 2547 . Springer , New York . 229--278.]] Zaroliagis, C. 2002. Implementations and experimental studies of dynamic graph algorithms. In Experimental Algorithmics, R. Fleischer, B. Moret, and E. M. Schmidt, Eds. LNCS, vol. 2547. Springer, New York. 229--278.]]"},{"key":"e_1_2_1_47_1","first-page":"2","article-title":"A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths","volume":"4","author":"Zhan F. B.","year":"2000","unstructured":"Zhan , F. B. and Noon , C. E. 2000 . A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths . Journal of Geographic Information and Decision Analysis 4 , 2 .]] Zhan, F. B. and Noon, C. E. 2000. A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths. Journal of Geographic Information and Decision Analysis 4, 2.]]","journal-title":"Journal of Geographic Information and Decision Analysis"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1064546.1103378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:09:57Z","timestamp":1672229397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1064546.1103378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,31]]},"references-count":47,"alternative-id":["10.1145\/1064546.1103378"],"URL":"https:\/\/doi.org\/10.1145\/1064546.1103378","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,31]]}}}