Shortest-path algorithms: Taxonomy and annotation

DOI10.1002/net.3230140208zbMath0542.90101MaRDI 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 scheme; annotated bibliography; shortest-path algorithms

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

65K05: Numerical mathematical programming methods

90C10: Integer programming

90B10: Deterministic network models in operations research

05C38: Paths and cycles

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

00A15: Bibliographies for mathematics in general

Related Items

Unnamed Item, Unnamed Item, The determination of the path with minimum-cost norm value, Unnamed Item, New polynomial time algorithms to compute a set of Pareto optimal paths for multi-objective shortest path problems, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, A simplification of the double-sweep algorithm to solve the \(k\)-shortest path problem, Graph theory (algorithmic, algebraic, and metric problems), Bounding probabilistic relationships in Bayesian networks using qualitative influences: methods and applications, A parametric approach to solving bicriterion shortest path problems, Location of central nodes in time varying computer networks, The quickest path problem, An interactive approach to identify the best compromise solution for two objective shortest path problems, The hierarchical network design problem, Transitive closure and related semiring properties via eliminants, A parallel shortest path algorithm, Parallel algorithms for the single source shortest path problem, Weighted min cost flows, An algorithm for finding the \(k\) quickest paths in a network, Network reduction for the acyclic constrained shortest path problem, The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm, On the quickest path problem, An algorithm for the ranking of shortest paths, Algorithms for the constrained quickest path problem and the enumeration of quickest paths, Finding the \(k\) quickest simple paths in a network, Dynamic expression trees, A simplicial decomposition algorithm for solving the variational inequality formulation of the general traffic assignment problem for large scale network, Minimum time paths in a network with mixed time constraints., On the sum-max bicriterion path problem., Minimization of travel time and weighted number of stops in a traffic-light network, Dynamic shortest path in stochastic dynamic networks: Ship routing problem, Finding \(K\) shortest looping paths in a traffic-light network, Intelligent transportation systems -- Enabling technologies, Searching among intervals and compact routing tables, Multiobjective transportation network design and routing problems: Taxonomy and annotation, New algorithms for multi objective shortest path problem., Efficient computation of shortest paths in networks using particle swarm optimization and noising metaheuristics, The first \(K\) shortest unique-arc walks in a traffic-light network, Symmetric connection problems and their solution by bidirectional search, Information tradeoffs in model building: A network routing application, Approximating the Stochastic Network by its M Shortest Paths, UTILIZING DISTRIBUTED LEARNING AUTOMATA TO SOLVE STOCHASTIC SHORTEST PATH PROBLEMS

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