Shortest-Route Methods: 1. Reaching, Pruning, and Buckets

Eric V. Denardo
Eric V. Denardo
Yale University, New Haven, Connecticut
Search for more papers by this author
,
Bennett L. Fox
Bennett L. Fox
University of Montreal, Montreal, Quebec
Search for more papers by this author

Eric V. Denardo

Yale University, New Haven, Connecticut

Search for more papers by this author

Bennett L. Fox

University of Montreal, Montreal, Quebec

Search for more papers by this author

Published Online:1 Feb 1979https://doi.org/10.1287/opre.27.1.161

Abstract

We present a new family of shortest-route methods, which reduce an upper bound on running time, and make empirical comparisons for a certain class of networks. These methods also allow for exploitation of structure by pruning arcs and/or nodes.

Cited by
- Exploring monotone priority queues for Dijkstra optimization
  23 June 2025 | RAIRO - Operations Research
- Enhanced methods for the weight constrained shortest path problem
  13 February 2024 | Networks, Vol. 84, No. 1
- Multi Bucket Queues: Efficient Concurrent Priority Scheduling
  17 June 2024
- An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance
  10 August 2022 | Optimization Letters, Vol. 17, No. 2
- JHeaps: An open-source library of priority queues
  SoftwareX, Vol. 16
- A novel pseudo‐polynomial approach for shortest path problems
  16 February 2021 | Networks, Vol. 78, No. 2
- Advanced Drainage and Pothole Navigation System Based on IoT
- Model for determining optimal routes in complex transport systems
  Transportation Research Procedia, Vol. 57
- Dynamic Programming Approaches for Solving Shortest Path Problem in Transportation: Comparison and Application
  24 March 2020
- Asynchronous Parallel Dijkstra’s Algorithm on Intel Xeon Phi Processor
  7 December 2018
- Customizable Route Planning in Road Networks
  Daniel Delling,
  Andrew V. Goldberg,
  Thomas Pajor,
  Renato F. Werneck
  22 May 2015 | Transportation Science, Vol. 51, No. 2
- Highway Dimension and Provably Efficient Shortest Path Algorithms
  8 December 2016 | Journal of the ACM, Vol. 63, No. 5
- Time-dependent Shortest Hyperpaths for Dynamic Routing on Transit Networks
  28 February 2017
- Road Reconstruction and Redundancy Analysis on the Road Network: A Case Study of the Ateneo de Manila University Network
  Procedia - Social and Behavioral Sciences, Vol. 218
- A New Approach to Incremental Cycle Detection and Related Problems
  8 December 2015 | ACM Transactions on Algorithms, Vol. 12, No. 2
- Route Planning in Transportation Networks
  11 November 2016
- Feasibility and issues for establishing network-based carpooling scheme
  Pervasive and Mobile Computing, Vol. 24
- Constrained shortest path problems: state-of-the-art and recent advances
- A branch-and-price approach for a multi-period vehicle routing problem
  Computers & Operations Research, Vol. 55
- Algebraic Theory on Shortest Paths for All Flows
  9 December 2015
- Backward Path Growth for Efficient Mobile Sequential Recommendation
  IEEE Transactions on Knowledge and Data Engineering, Vol. 27, No. 1
- Real-timefastest path algorithm using bidirectional point-to-point search on a Fuzzy Time-Dependent transportation network
- Sharing information for the all pairs shortest path problem
  Theoretical Computer Science, Vol. 520
- A survey of resource constrained shortest path problems: Exact solution approaches
  6 June 2013 | Networks, Vol. 62, No. 3
- PHAST: Hardware-accelerated shortest path trees
  Journal of Parallel and Distributed Computing, Vol. 73, No. 7
- A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS
  4 April 2013 | Asia-Pacific Journal of Operational Research, Vol. 30, No. 02
- Some Problems of Rational Route Choice for a City Road Network
  2 September 2013
- HLDB
  6 November 2012
- Route selection for best distances in road databases based on drivers’ and customers’ preferences
  Canadian Journal of Forest Research, Vol. 42, No. 6
- On Some Special Network Flow Problems: The Shortest Path Tour Problems
  1 July 2012
- Complexity analysis and optimization of the shortest path tour problem
  6 November 2010 | Optimization Letters, Vol. 6, No. 1
- The orienteering problem with stochastic travel and service times
  26 May 2011 | Annals of Operations Research, Vol. 186, No. 1
- Finding the dominant energy transmission paths in statistical energy analysis
  Journal of Sound and Vibration, Vol. 330, No. 10
- PHAST: Hardware-Accelerated Shortest Path Trees
- Shortest-path feasibility algorithms
  5 January 2010 | ACM Journal of Experimental Algorithmics, Vol. 14
- An extension of labeling techniques for finding shortest path trees
  European Journal of Operational Research, Vol. 198, No. 1
- Generalized network Voronoi diagrams: Concepts, computational methods, and applications
  International Journal of Geographical Information Science, Vol. 22, No. 9
- A Reach and Bound algorithm for acyclic dynamic‐programming networks
  14 December 2007 | Networks, Vol. 52, No. 1
- A shortest path algorithm for moving objects in spatial network databases
  Progress in Natural Science, Vol. 18, No. 7
- Accelerating the Neighbor-Joining Algorithm Using the Adaptive Bucket Data Structure
- A Practical Shortest Path Algorithm with Linear Expected Time
  SIAM Journal on Computing, Vol. 37, No. 5
- Point-to-Point Shortest Path Algorithms with Preprocessing
- The shortest path problem on large‐scale real‐road networks
  30 August 2006 | Networks, Vol. 48, No. 4
- Heuristic shortest path algorithms for transportation applications: State of the art
  Computers & Operations Research, Vol. 33, No. 11
- Shortest Path Algorithms
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
  Journal of Computer and System Sciences, Vol. 69, No. 3
- Resource Constrained Shortest Path Problems in Path Planning for Fleet Management
  Journal of Mathematical Modelling and Algorithms, Vol. 3, No. 1
- Shortest-Paths Trees
- Δ-stepping: a parallelizable shortest path algorithm
  Journal of Algorithms, Vol. 49, No. 1
- Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
  Journal of Algorithms, Vol. 48, No. 1
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
  9 June 2003
- A new algorithm for reoptimizing shortest paths when the arc costs change
  Operations Research Letters, Vol. 31, No. 2
- The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
  15 July 2002 | RAIRO - Operations Research, Vol. 36, No. 1
- Integrating GIS, GPS and GSM technologies for the effective management of ambulances
  Computers, Environment and Urban Systems, Vol. 25, No. 3
- A Simple Shortest Path Algorithm with Linear Average Time
  17 August 2001
- Shortest Path Algorithms: Engineering Aspects
  4 December 2001
- Non-Static Network Optimization Problems: A Survey
- Efficient modeling of travel in networks with time-varying link speeds
  1 January 2000 | Networks, Vol. 36, No. 2
- Dynamic programming using the Fritz–John conditions
  European Journal of Operational Research, Vol. 123, No. 1
- Transformations and Exact Node Routing Solutions by Column Generation
- On RAM Priority Queues
  SIAM Journal on Computing, Vol. 30, No. 1
- DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS
  30 April 2012 | International Journal of Foundations of Computer Science, Vol. 10, No. 03
- Buckets, Heaps, Lists, and Monotone Priority Queues
  SIAM Journal on Computing, Vol. 28, No. 4
- Shortest Path Algorithms In Transportation Models: Classical and Innovative Aspects
- Implementations of Dijkstra’s Algorithm Based on Multi-Level Buckets
- A Computational Method for Market Area Analysis on a Network
  3 September 2010 | Geographical Analysis, Vol. 28, No. 4
- Shortest paths algorithms: Theory and experimental evaluation
  Mathematical Programming, Vol. 73, No. 2
- Negative-cycle detection algorithms
  6 June 2005
- Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille
  29 March 2011 | RAIRO - Operations Research, Vol. 30, No. 4
- Multiobjective routing problems
  Top, Vol. 3, No. 2
- Chapter 2 Time constrained routing and scheduling
- Bibliography
  27 May 2008
- Case Study in Coordination
- Extracting curvilinear features from remotely sensed images using minimum cost path techniques
- An algorithm for the ranking of shortest paths
  European Journal of Operational Research, Vol. 69, No. 1
- Routing with nonlinear multiattribute cost functions
  Applied Mathematics and Computation, Vol. 54, No. 2-3
- Single machine scheduling with flow time and earliness penalties
  Journal of Global Optimization, Vol. 3, No. 3
- Deployment of robotic agents in uncertain environments: game theoretic rules and simulation studies
  27 February 2009 | Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Vol. 6, No. 1
- The Linear Assignment Problem
- I/O-efficiency of shortest path algorithms: an analysis
- Searching time-table networks
  27 February 2009 | Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Vol. 5, No. 3
- Some Recent Advances in Network Flows
  SIAM Review, Vol. 33, No. 2
- Shortest path algorithms: A computational study with the C programming language
  Computers & Operations Research, Vol. 18, No. 8
- An algorithm-structured neural net for the shortest-path problem
- Faster algorithms for the shortest path problem
  1 April 1990 | Journal of the ACM, Vol. 37, No. 2
- Literaturverzeichnis
- Generalized dynamic programming for multicriteria optimization
  European Journal of Operational Research, Vol. 44, No. 1
- A transport span protection strategy for survivability of interoffice facilities telecommunications networks
- Chapter IV Network flows
- Shortest path algorithms
  Annals of Operations Research, Vol. 13, No. 1
- Recent developments in path finding algorithms: a review
  Transportation Planning and Technology, Vol. 12, No. 1
- A reoptimization algorithm for the shortest path problem with time windows
  European Journal of Operational Research, Vol. 35, No. 2
- A computational study of efficient shortest path algorithms
  Computers & Operations Research, Vol. 15, No. 6
- A dynamically-directed switch model for MOS logic simulation
- Critical path analysis for the execution of parallel and distributed programs
- Hybrid Dynamic Programming/Branch-and-Bound Strategies for Electric Power Generation Planning
  IIE Transactions, Vol. 18, No. 2
- Microcomputer-based algorithms for large scale shortest path problems
  Discrete Applied Mathematics, Vol. 13, No. 2-3
- Shortest path methods: A unifying approach
  26 February 2009
- Shortest paths in networks with vector weights
  Journal of Optimization Theory and Applications, Vol. 46, No. 1
- Coroutines in the Unified-System operating system
  Cybernetics, Vol. 21, No. 1
- Practical use of Bucketing Techniques in Computational Geometry
- An algorithm for ranking paths that may contain cycles
  European Journal of Operational Research, Vol. 18, No. 1
- On a special class of bicriterion path problems
  European Journal of Operational Research, Vol. 17, No. 1
- Shortest‐path methods: Complexity, interrelations and new propositions
  11 October 2006 | Networks, Vol. 14, No. 2
- Shortest‐path algorithms: Taxonomy and annotation
  11 October 2006 | Networks, Vol. 14, No. 2
- Alternative group relaxation of integer programming problems
  Discrete Applied Mathematics, Vol. 8, No. 2
- Optimal control of water distribution systems by network flow theory
  IEEE Transactions on Automatic Control, Vol. 29, No. 4
- Computational study of an improved shortest path algorithm
  11 October 2006 | Networks, Vol. 14, No. 1
- A dynamic programming algorithm for multiple-choice constraints
  Computers & Mathematics with Applications, Vol. 10, No. 3
- Shortest Paths in Signed Graphs
- Anticenters and antimedians of a network
  9 March 2007 | Networks, Vol. 13, No. 3
- An alternative for the implementation of Kruskal's minimal spanning tree algorithm
  Science of Computer Programming, Vol. 3, No. 2
- Routing and scheduling of vehicles and crews
  Computers & Operations Research, Vol. 10, No. 2
- Nonlinear integer programming for various forms of constraints
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 29, No. 4
- An efficient algorithm for K shortest simple paths
  11 October 2006 | Networks, Vol. 12, No. 4
- Recent Developments in Computer Implementation Technology for Network Flow Algorithms
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 20, No. 4
- Multiobjective Energy Generation Planning Under Uncertainty
  9 July 2007 | A I I E Transactions, Vol. 14, No. 3
- Modified group minimization algorithm using support elements
  USSR Computational Mathematics and Mathematical Physics, Vol. 22, No. 3
- A new algorithm to find the shortest paths between all pairs of nodes
  Discrete Applied Mathematics, Vol. 4, No. 1
- A dual simplex algorithm for finding all shortest paths
  11 October 2006 | Networks, Vol. 11, No. 4
- Order preserving extendible hashing and bucket tries
  BIT, Vol. 21, No. 4
- Heuristics and their design: a survey
  European Journal of Operational Research, Vol. 8, No. 1
- Current and future research directions in network optimization
  Computers & Operations Research, Vol. 8, No. 2
- An O(tm log D) Algorithm for shortest paths
  Discrete Applied Mathematics, Vol. 2, No. 2
- Reoptimization procedures in shortest path problem
  Rivista di Matematica per le Scienze Economiche e Sociali, Vol. 3, No. 1
- Alternative group relaxation of integer programming problems

Volume 27, Issue 1

January-February 1979

Pages 1-207

Article Information

Metrics

Information

Published Online:February 01, 1979

Cite as

Eric V. Denardo, Bennett L. Fox, (1979) Shortest-Route Methods: 1. Reaching, Pruning, and Buckets. Operations Research 27(1):161-186.

https://doi.org/10.1287/opre.27.1.161

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Shortest-Route Methods: 1. Reaching, Pruning, and Buckets

Abstract

Volume 27, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News