Finding the k Shortest Paths

DOI10.1137/S0097539795290477zbMath0912.05057MaRDI QIDQ4210169

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

dynamic programming network programming knapsack problem shortest paths genealogy inscribed polygon sequence alignment near-optimal solutions path enumeration

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (only showing first 100 items - show all)

Path flow estimator in an entropy model using a nonlinear L-shaped algorithm ⋮ Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach ⋮ Heuristic search for one-to-many shortest path queries ⋮ The minmax regret robust shortest path problem in a finite multi-scenario model ⋮ Development of a railway out-of-gauge freight transport routing optimal method ⋮ Computing strictly-second shortest paths ⋮ Multicriteria movement synchronization scheduling problems and algorithms ⋮ A heuristic for optimizing stochastic activity networks with applications to statistical digital circuit sizing ⋮ Finding next-to-shortest paths in a graph ⋮ An exact algorithm for the robust shortest path problem with interval data ⋮ Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context ⋮ Finding $K$ shortest looping paths in a traffic-light network ⋮ Fast computation of bounds for two-terminal network reliability ⋮ $k$-shortest routing of trains on shunting yards ⋮ Computing and listing $st$-paths in public transportation networks ⋮ On the cardinality of the Pareto set in bicriteria shortest path problems ⋮ A decision-theoretic approach to robust optimization in multivalued graphs ⋮ Multiple-path selection for new highway alignments using discrete algorithms ⋮ The most probable annotation problem in HMMs and its application to bioinformatics ⋮ Finding the $K$ shortest paths in a time-schedule network with constraints on arcs ⋮ Generalized route planning model for hazardous material transportation with VaR and equity considerations ⋮ Constructing the nearly shortest path in crossed cubes ⋮ A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem ⋮ Bounds on the complexity of halfspace intersections when the bounded faces have small dimension ⋮ Applications of Weighted Automata in Natural Language Processing ⋮ Theoretical insights and algorithmic tools for decision diagram-based optimization ⋮ Solving a constrained economic lot size problem by ranking efficient production policies ⋮ Choquet-based optimisation in multiobjective shortest path and spanning tree problems ⋮ A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems ⋮ Algorithms for shortest paths and $d$-cycle problems ⋮ A fast method for discovering critical edge sequences in e-commerce catalogs ⋮ Approximating the Canadian traveller problem with online randomization ⋮ Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks ⋮ On the online multi-agent O-D $k$-Canadian traveler problem ⋮ Efficiently Listing Bounded Length st-Paths ⋮ On the Disambiguation of Weighted Automata ⋮ How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis ⋮ Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ Finding $K$ dissimilar paths: single-commodity and discretized flow formulations ⋮ Minimal counterexamples for linear-time probabilistic verification ⋮ Priority-oriented route network planning for evacuation in constrained space scenarios ⋮ Algorithm for resource allocation in data centers with independent schedulers for different types of resources ⋮ Efficient enumeration of weighted tree languages over the tropical semiring ⋮ Emergency evacuation problem for a multi-source and multi-destination transportation network: mathematical model and case study ⋮ Providing Evidence of Likely Being on Time: Counterexample Generation for CTMC Model Checking ⋮ K$^{\ast}$: A heuristic search algorithm for finding the $k$ shortest paths ⋮ Novel node-ranking approach for SDN-based virtual network embedding ⋮ Speeding up Martins' algorithm for multiple objective shortest path problems ⋮ Generating counterexamples for quantitative safety specifications in probabilistic B ⋮ Finding the first $K$ shortest paths in a time-window network. ⋮ Splitting (complicated) surfaces is hard ⋮ Low time complexity algorithms for path computation in Cayley graphs ⋮ Exact and heuristic solution approaches for the integrated job scheduling and constrained network routing problem ⋮ Finding a given number of solutions to a system of fuzzy constraints ⋮ Network majority on tree topological network ⋮ The global optimal algorithm of reliable path finding problem based on backtracking method ⋮ Algorithms for finding the weight-constrained $k$ longest paths in a tree and the length-constrained $k$ maximum-sum segments of a sequence ⋮ Computational convergence of the path integral for real dendritic morphologies ⋮ A novel single source shortest path algorithm ⋮ Multicriteria path and tree problems: discussion on exact algorithms and applications ⋮ Finding the $K$ shortest paths in a schedule-based transit network ⋮ Origin-destination matrix estimation problem in a Markov chain approach ⋮ Minimal functional routes in directed graphs with dependent edges ⋮ Finding the $K$ shortest hyperpaths ⋮ The first $K$ shortest unique-arc walks in a traffic-light network ⋮ Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey ⋮ Solving the constrained shortest path problem using random search strategy ⋮ Improved algorithms for the $k$ simple shortest paths and the replacement paths problems ⋮ Applications of Page Ranking in P Systems ⋮ Multi-route planning of multimodal transportation for oversize and heavyweight cargo based on reconstruction ⋮ Finding $K$ shortest looping paths with waiting time in a time--window network ⋮ A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool ⋮ Balanced-flow algorithm for path network planning in hierarchical spaces ⋮ An Efficient Best-Trees Algorithm for Weighted Tree Automata over the Tropical Semiring ⋮ A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs ⋮ Efficient Generation of Top-k Procurements in a Multi-item Auction ⋮ Combination of piecewise-geodesic paths for interactive segmentation ⋮ Solving the $k$-shortest path problem with time windows in a time varying network ⋮ The shortest path problem with forbidden paths ⋮ Unnamed Item ⋮ Efficient meta-data structure in top-$k$ queries of combinations and multi-item procurement auctions ⋮ Efficient single-pair all-shortest-path query processing for massive dynamic networks ⋮ Efficiently Generating k-Best Solutions to Procurement Auctions ⋮ Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles ⋮ Multi-objective evacuation routing in transportation networks ⋮ Candidate Sets for Alternative Routes in Road Networks ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ An efficient algorithm to find next-to-shortest path on permutation graphs ⋮ Distributionally robust maximum probability shortest path problem ⋮ The one-dimensional cutting stock problem with due dates ⋮ Distance confined path problem and separable integer programming ⋮ Flows with unit path capacities and related packing and covering problems ⋮ Two-best solutions under distance constraints: The model and exemplary results for matroids ⋮ $k$-best solutions under distance constraints in valuated $\Delta$-matroids ⋮ Small-$m$ method for detecting all longest paths ⋮ Optimal shortest path set problem in undirected graphs ⋮ Solving some lexicographic multi-objective combinatorial problems ⋮ Unified approach to fuzzy graph problems ⋮ A disambiguation algorithm for weighted automata

Cites Work

This page was built for publication: Finding the k Shortest Paths