Shortest paths algorithms: Theory and experimental evaluation
From MaRDI portal
Publication:1919099
DOI10.1007/BF02592101zbMath0853.90111OpenAlexW3137299218WikidataQ28048899 ScholiaQ28048899MaRDI QIDQ1919099
Tomasz Radzik, Boris V. Cherkassky, Andrew V. Goldberg
Publication date: 20 October 1996
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02592101
Related Items
IBM ILOG CP optimizer for scheduling. 20+ years of scheduling with constraints at IBM/ILOG ⋮ Flow distances on open flow networks ⋮ Shortest path reoptimization vs resolution from scratch: a computational comparison ⋮ Efficient transitive closure of sparse matrices over closed semirings ⋮ On residual approximation in solution extension problems ⋮ Event counting of partially-observed discrete-event systems with uniformly and nonuniformly bounded diagnosis delays ⋮ New efficient shortest path simplex algorithm: Pseudo permanent labels instead of permanent labels ⋮ An exact method for the biobjective shortest path problem for large-scale road networks ⋮ Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm ⋮ Rank-Sensitive Priority Queues ⋮ hCHAC: a family of MOACO algorithms for the resolution of the bi-criteria military unit pathfinding problem ⋮ A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem ⋮ The vehicle rescheduling problem with retiming ⋮ On an exact method for the constrained shortest path problem ⋮ On Some Special Network Flow Problems: The Shortest Path Tour Problems ⋮ Two fast algorithms for all-pairs shortest paths ⋮ Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points ⋮ Optimal placement of UV-based communications relay nodes ⋮ Two-level heaps: a new priority queue structure with applications to the single source shortest path problem ⋮ A robust optimization model for distribution network design under a mixed integer set of scenarios ⋮ Unnamed Item ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ A fully polynomial time approximation scheme for the probability maximizing shortest path problem ⋮ Sharing information for the all pairs shortest path problem ⋮ The weak-heap data structure: variants and applications ⋮ Hyperspherical embedding of graphs and networks in communicability spaces ⋮ Priority-oriented route network planning for evacuation in constrained space scenarios ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ Path Laplacian matrices: introduction and application to the analysis of consensus in networks ⋮ Emergency evacuation problem for a multi-source and multi-destination transportation network: mathematical model and case study ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ Finding the shortest paths by node combination ⋮ A certifying algorithm for lattice point feasibility in a system of UTVPI constraints ⋮ An efficient label setting/correcting shortest path algorithm ⋮ Using software complexity measures to analyze algorithms -- an experiment with the shortest-paths algorithms. ⋮ An efficient time and space \(K\) point-to-point shortest simple paths algorithm ⋮ Optimization of heuristic search using recursive algorithm selection and reinforcement learning ⋮ Tree-Deletion Pruning in Label-Correcting Algorithms for the Multiobjective Shortest Path Problem ⋮ A parallel bio-inspired shortest path algorithm ⋮ Fuzzy shortest path problems incorporating interactivity among paths. ⋮ New models for shortest path problem with fuzzy arc lengths ⋮ Ordered weighted average combinatorial optimization: formulations and their properties ⋮ Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem ⋮ A reduction approach to the two-campus transport problem ⋮ Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks ⋮ A network model for routing-fault-free wavelength selection in WRONoCs design ⋮ A zero-space algorithm for negative cost cycle detection in networks ⋮ An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection ⋮ A comparison of solution strategies for biobjective shortest path problems ⋮ Complexity analysis and optimization of the shortest path tour problem ⋮ Route planning with turn restrictions: A computational experiment ⋮ Dynamic programming approaches to solve the shortest path problem with forbidden paths ⋮ Shortest-path queries in static networks ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Algebraic Theory on Shortest Paths for All Flows ⋮ Dynamic programming for spanning tree problems: application to the multi-objective case ⋮ A spectral approach to the shortest path problem ⋮ Heuristic shortest path algorithms for transportation applications: state of the art ⋮ The problem of synthesis of reliable networks ⋮ A minmax regret version of the time-dependent shortest path problem ⋮ Shortest path tour problem with time windows ⋮ An auction-based approach for the re-optimization shortest path tree problem ⋮ Balanced-flow algorithm for path network planning in hierarchical spaces ⋮ Path optimization with limited sensing ability ⋮ A novel chaotic particle swarm optimization algorithm for parking space guidance ⋮ On the shortest path problem with negative cost cycles ⋮ Hydraulic modelling of closed pipes in loop equations of water distribution networks ⋮ A minmax regret approach to the critical path method with task interval times ⋮ Optimal path discovery problem with homogeneous knowledge ⋮ Intermittent fault diagnosability of discrete event systems: an overview of automaton-based approaches ⋮ Multiple UAVs path planning algorithms: a comparative study ⋮ LP-oriented upper bounds for the weighted stability number of a graph ⋮ Shortest paths with ordinal weights ⋮ A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time ⋮ Two-Levels-Greedy: a generalization of Dijkstra's shortest path algorithm ⋮ Deep learning Gauss-Manin connections ⋮ Solving the shortest path tour problem
Uses Software
Cites Work
- A note on two problems in connexion with graphs
- A computational study of efficient shortest path algorithms
- Shortest path algorithms: A computational study with the C programming language
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- A heuristic improvement of the Bellman-Ford algorithm
- A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
- On a routing problem
- Faster algorithms for the shortest path problem
- A New Polynomially Bounded Shortest Path Algorithm
- Shortest‐path methods: Complexity, interrelations and new propositions
- Threshold assignment algorithm
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Properties of Labeling Methods for Determining Shortest Path Trees
- Design and implementation of an efficient priority queue
- Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
- Faster Scaling Algorithms for Network Problems
- Implementation and efficiency of Moore-algorithms for the shortest route problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
