Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
Operations ResearchPublished 1 February 1979
Eric V. Denardo, Bennett L. Fox
Citations197
SJR quartileQ1
SJR score2.56
SNIP1.83
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new family of shortest-route methods are presented, which reduce an upper bound on running time, and make empirical comparisons for a certain class of networks, and allow for exploitation of structure by pruning arcs and/or nodes.
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.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
RePEc: Research Papers in EconomicsInteger programming
3,383 Citations1972G. L. Nemhauser, Laurence A. Wolsey
Quarterly of Applied MathematicsOn a routing problem
2,695 Citations1958Richard Bellman
Given a set of N cities, with every two linked by a road, and the times required to traverse these roads, the functional equation technique of dynamic programming and approximation in policy space yield an iterative algorithm which converges after at most (N-1) iterations.
Journal of the ACMEfficient Algorithms for Shortest Paths in Sparse Networks
1,048 Citations1977D. Barton Johnson
Algorithms for finding shortest paths are presented which are faster than algorithms previously known on networks which are relatively sparse in arcs, and a class of “arc set partition” algorithms is introduced.
Operations ResearchAn Appraisal of Some Shortest-Path Algorithms
997 Citations1969Stuart E. Dreyfus
This paper treats five discrete shortest-path problems: determining the shortest path between two specified nodes of a network, determining the second, third, etc., shortest path, finding the fastest path through a network with travel times depending on the departure time, and finding the shortest paths between specified endpoints that passes through specified intermediate nodes.
Operations ResearchThe Theory and Computation of Knapsack Functions
607 Citations1966Paul C. Gilmore, Ralph E. Gomory
This paper gives a characterization of knapsack functions and then uses the characterization to develop more efficient methods of computation.
Communications of the ACMAlgorithm 360: shortest-path forest with topological ordering [H]
368 Citations1969Robert B. Dial
This method might be called a “paper strip method” for analysis of variance and is similar to paper strip methods used for operations with polynomials.
Journal of the ACMA Note on Dijkstra's Shortest Path Algorithm
317 Citations1973D. Barton Johnson
An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O(n)(supscrpt) steps is disproved by showing a set of networks which take O (O) 2 (n) 3 steps.
Management ScienceDiscrete Dynamic Programming and Capital Allocation
230 Citations1969George L. Nemhauser, Zev Ullmann
This work extends the work of Weingartner and Ness by including multilevel projects, reinvesting returns, borrowing and lending, capital deferrals, and project interactions, and is able to handle dynamic programming models with several state variables because the optimal returns are monotone non-decreasing step functions.
NetworksA computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
224 Citations1979Roman Dial, Fred Glover +2 more
The study shows that the procedures examined indeed exert a powerful influence on solution efficiency, with the identity of the best dependent upon the topology of the network and the range of the arc distance coefficients.
Mathematical ProgrammingImplementation and efficiency of Moore-algorithms for the shortest route problem
214 Citations1974Uwe Pape
The main objective of this paper is to show the strong relationship between an algorithm and its implementation and to show a variant of Moore's method seems to be most efficient for different types of graph structures.
Operations ResearchBranch-and-Bound Strategies for Dynamic Programming
172 Citations1976Thomas L. Morin, Roy E. Marsten
This paper shows how branch-and-bound methods can be used to reduce storage and, possibly, computational requirements in discrete dynamic programs.
DSpace@MIT (Massachusetts Institute of Technology)Shortest-Path Algorithms: A Comparison
94 Citations1975Bruce Golden
The objective is to present some computational experience to support the claim that a version of Bellman's shortest-path algorithm outperforms Treesort-Dijkstra's for a certain class of networks and indicates that Pape's reluctance to use a variable length list of rmodes to be scanned is unwarranted.
Management ScienceAn Algorithm for Nonlinear Knapsack Problems
86 Citations1976Thomas L. Morin, Roy E. Marsten
An algorithm which recursively generates the complete family of undominated feasible solutions to separable nonlinear multidimensional knapsack problems is developed by exploiting discontinuity preserving properties of the maximal convolution.
A performance comparison of labeling algorithms for calculating shortest path trees
72 Citations1973Judith F Gilsinn
Transportation ResearchImproved shortest path algorithms for transport networks
61 Citations1978Dirck Van Vliet
The three most appropriate algorithms for calculating shortest paths in transport road networks—those due to Moore, D'Esopo and Dijkstra—are examined using CPU times on five realistic networks as criteria and their relative efficiencies are shown to depend on certain characteristics of the network.
Journal of the ACMA Shortest Path Algorithm for Edge-Sparse Graphs
49 Citations1976Robert A. Wagner
An algorithm (FLOW) for finding the shortest distance from a given node S to each node X of a directed graph with nonnegative integer arc lengths less than or equal to WM is presented and is compared with its best-known competitor, that of Dijkstra and Yen (DFLO).
On shortest paths and sorting
41 Citations1972Ellis L. Johnson
It is shown how algorithms from sorting literature can be used to accomplish this part of the shortest path algorithm, and bounds on the largest possible amount of work are established.
Operations ResearchData Structures and Computer Science Techniques in Operations Research
38 Citations1978Bennett L. Fox
Some important data structures and computer science techniques, and their applications to operations research problems are discussed, and some of which are novel are novel.
Operations ResearchShortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
26 Citations1979Eric V. Denardo, Bennett L. Fox
New, fast methods for handling two types of group knapsack networks—those having only unbounded variables and those having some bounded variables are contained in a new branch-and-bound scheme for pure integer programs.
A COMPARATIVE INVESTIGATION OF THE COMPUTATIONAL EFFICIENCY OF SHORTEST PATH ALGORITHMS
19 Citations1968Lewis E. Hitchner
An investigation of five algorithms for finding the shortest path from a root node to all other nodes for different network structures found that one is best suited for their problem.