Shortest-path algorithms: Taxonomy and annotation

DOI10.1002/NET.3230140208zbMath0542.90101OpenAlexW2063317962MaRDI QIDQ3330993

Narsingh Deo, Chiyin Pang

Publication date: 1984

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230140208

zbMATH Keywords

classification schemeannotated bibliographyshortest-path algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Bibliographies for mathematics in general (00A15)

Related Items (59)

The hierarchical network design problem ⋮ Multiobjective transportation network design and routing problems: Taxonomy and annotation ⋮ Transitive closure and related semiring properties via eliminants ⋮ Finding \(K\) shortest looping paths in a traffic-light network ⋮ Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network ⋮ Dynamic expression trees ⋮ Searching among intervals and compact routing tables ⋮ Multi-objective particle swarm optimization for mechanical harvester route planning of sugarcane field operations ⋮ Analysis of FPTASes for the multi-objective shortest path problem ⋮ Intelligent transportation systems -- Enabling technologies ⋮ A parallel shortest path algorithm ⋮ A simplicial decomposition algorithm for solving the variational inequality formulation of the general traffic assignment problem for large scale network ⋮ Searching among intervals and compact routing tables ⋮ Analyzing the reachability problem in choice networks ⋮ On Some Special Network Flow Problems: The Shortest Path Tour Problems ⋮ An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem ⋮ Symmetric connection problems and their solution by bidirectional search ⋮ Upgrading edges in the graphical TSP ⋮ Reachability in choice networks ⋮ Lower bounds for non-adaptive shortest path relaxation ⋮ Minimum time paths in a network with mixed time constraints. ⋮ On the sum-max bicriterion path problem. ⋮ Unnamed Item ⋮ The quickest path problem ⋮ An interactive approach to identify the best compromise solution for two objective shortest path problems ⋮ Parallel algorithms for the single source shortest path problem ⋮ Weighted min cost flows ⋮ Optimal paths in bi-attribute networks with fractional cost functions ⋮ Distributed shortest-path protocols for time-dependent networks ⋮ A new algorithm to compute Pareto-optimal paths in a multi objective fuzzy weighted network ⋮ Unnamed Item ⋮ New polynomial time algorithms to compute a set of Pareto optimal paths for multi-objective shortest path problems ⋮ New algorithms for multi objective shortest path problem. ⋮ An algorithm for finding the \(k\) quickest paths in a network ⋮ Efficient computation of shortest paths in networks using particle swarm optimization and noising metaheuristics ⋮ Complexity analysis and optimization of the shortest path tour problem ⋮ Network reduction for the acyclic constrained shortest path problem ⋮ A simplification of the double-sweep algorithm to solve the \(k\)-shortest path problem ⋮ Dynamic programming approaches to solve the shortest path problem with forbidden paths ⋮ The first \(K\) shortest unique-arc walks in a traffic-light network ⋮ Solving the constrained shortest path problem using random search strategy ⋮ Shortest-path queries in static networks ⋮ Bounding probabilistic relationships in Bayesian networks using qualitative influences: methods and applications ⋮ Efficient modeling of travel in networks with time-varying link speeds ⋮ The determination of the path with minimum-cost norm value ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Information tradeoffs in model building: A network routing application ⋮ The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm ⋮ On the quickest path problem ⋮ Approximating the Stochastic Network by its M Shortest Paths ⋮ UTILIZING DISTRIBUTED LEARNING AUTOMATA TO SOLVE STOCHASTIC SHORTEST PATH PROBLEMS ⋮ An algorithm for the ranking of shortest paths ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ Algorithms for the constrained quickest path problem and the enumeration of quickest paths ⋮ A parametric approach to solving bicriterion shortest path problems ⋮ Location of central nodes in time varying computer networks ⋮ Finding the \(k\) quickest simple paths in a network ⋮ Minimization of travel time and weighted number of stops in a traffic-light network ⋮ Dynamic shortest path in stochastic dynamic networks: Ship routing problem

Cites Work

• Unnamed Item
• A Method for the Solution of the N th Best Path Problem
• Computational experience with an algorithm for finding the k shortest paths in a network
• A Shortest Path Algorithm for Edge-Sparse Graphs
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Sparse matrix techniques for the shortest path problem
• On the determination of the shortes path in a network having gains
• Finding the Shortest Route between Two Points in a Network
• Some Computational Notes on the Shortest Route Problem
• Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N ³ Additions and N ³ Comparisons
• Determination of shortest path in a network with time-dependent edge-lengths¹
• CalculatingKth Shortest Paths
• A Note on Dijkstra's Shortest Path Algorithm
• A Note on Yen's Algorithm for Finding the Length of All Shortest Paths in N -Node Nonnegative-Distance Networks

This page was built for publication: Shortest-path algorithms: Taxonomy and annotation