Finding the k Shortest Paths
From MaRDI portal
Publication:4210169
DOI10.1137/S0097539795290477zbMATH Open0912.05057MaRDI QIDQ4210169FDOQ4210169
Authors: David Eppstein 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Finding the \(K\) shortest hyperpaths
- Finding shortest and dissimilar paths
- Finding \(k\) simple shortest paths and cycles
- Finding the K Shortest Loopless Paths in a Network
- Finding the k shortest simple paths
- Finding the \(k\) quickest simple paths in a network
- An efficient implementation of an algorithm for findingK shortest simple paths
- Finding the Minimum-Weight k-Path
- Near-shortest and K-shortest simple paths
dynamic programmingshortest pathsgenealogyknapsack problemsequence alignmentnetwork programminginscribed polygonnear-optimal solutionspath enumeration
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Applications of graph theory to circuits and networks (94C15)
Cites Work
- Title not available (Why is that?)
- On a routing problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- An algorithm for ranking paths that may contain cycles
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Title not available (Why is that?)
- Scaling Algorithms for the Shortest Paths Problem
- Disjoint paths in a network
- Finding the K Shortest Loopless Paths in a Network
- Faster algorithms for the shortest path problem
- A priority queue in which initialization and queue operations takeO(loglogD) time
- An Appraisal of Some Shortest-Path Algorithms
- Separator based sparsification for dynamic planar graph algorithms
- Algorithms for the quickest path problem and the enumeration of quickest paths
- An algorithm for finding the \(k\) quickest paths in a network
- Finding the \(k\) quickest simple paths in a network
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
- An efficient algorithm for K shortest simple paths
- Faster shortest-path algorithms for planar graphs
- An optimal algorithm for selection in a min-heap
- Algorithms for proximity problems in higher dimensions
- Implementation of algorithms forK shortest loopless paths
- Title not available (Why is that?)
- On algorithms for finding the k shortest paths in a network
- Technical Note—Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming
- Iterative methods for determining the k shortest paths in a network
- Comment on a computing the k shortest paths in a graph
- A Note on an Algebra for the k Best Routes in a Network
- Semirings and path spaces
- An algebra for determining all path-values in a network with application to K-shortest-paths problems
- On computing sets of shortest paths in a graph
- All paths in an activity network
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Heuristic search for one-to-many shortest path queries
- Applications of Weighted Automata in Natural Language Processing
- Minimal counterexamples for linear-time probabilistic verification
- K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths
- A heuristic for optimizing stochastic activity networks with applications to statistical digital circuit sizing
- Finding \(K\) shortest looping paths with waiting time in a time--window network
- Solving the \(k\)-shortest path problem with time windows in a time varying network
- Finding shortest and dissimilar paths
- Choquet-based optimisation in multiobjective shortest path and spanning tree problems
- Implementation of algorithms forK shortest loopless paths
- Title not available (Why is that?)
- Theoretical insights and algorithmic tools for decision diagram-based optimization
- \(k\)-shortest routing of trains on shunting yards
- Solving the constrained shortest path problem using random search strategy
- The most probable annotation problem in HMMs and its application to bioinformatics
- The minmax regret robust shortest path problem in a finite multi-scenario model
- An efficient algorithm to find next-to-shortest path on permutation graphs
- Computing strictly-second shortest paths
- Title not available (Why is that?)
- Multi-objective evacuation routing in transportation networks
- The one-dimensional cutting stock problem with due dates
- Fast computation of bounds for two-terminal network reliability
- Computingk-shortest path lengths in euclidean networks
- Small-\(m\) method for detecting all longest paths
- Finding the k shortest simple paths
- Algorithms for shortest paths and \(d\)-cycle problems
- A fast method for discovering critical edge sequences in e-commerce catalogs
- Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks
- Finding theKth shortest path in a time-schedule network
- Finding the \(K\) shortest paths in a schedule-based transit network
- Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
- On the \(K\) shortest path trees problem
- How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis
- Multicriteria path and tree problems: discussion on exact algorithms and applications
- Multiple-path selection for new highway alignments using discrete algorithms
- Finding the Minimum-Weight k-Path
- Generalized route planning model for hazardous material transportation with VaR and equity considerations
- Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms
- Near-shortest and K-shortest simple paths
- An exact algorithm for the robust shortest path problem with interval data
- Algorithm for resource allocation in data centers with independent schedulers for different types of resources
- Finding the \(K\) shortest paths in a time-schedule network with constraints on arcs
- An experimental study on approximating \(k\) shortest simple paths
- Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
- The shortest path problem with forbidden paths
- Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
- A decision-theoretic approach to robust optimization in multivalued graphs
- Finding next-to-shortest paths in a graph
- Splitting (complicated) surfaces is hard
- Emergency evacuation problem for a multi-source and multi-destination transportation network: mathematical model and case study
- Exact and heuristic solution approaches for the integrated job scheduling and constrained network routing problem
- A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool
- A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems
- On the cardinality of the Pareto set in bicriteria shortest path problems
- Finding the \(K\) shortest hyperpaths
- Generating counterexamples for quantitative safety specifications in probabilistic B
- Computational convergence of the path integral for real dendritic morphologies
- Finding the first \(K\) shortest paths in a time-window network.
- An algorithm for finding all thek-components of a digraph
- Network majority on tree topological network
- Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey
- An efficient implementation of an algorithm for findingK shortest simple paths
- Finding \(K\) shortest looping paths in a traffic-light network
- Constructing the nearly shortest path in crossed cubes
- Optimal shortest path set problem in undirected graphs
- Solving some lexicographic multi-objective combinatorial problems
- Unified approach to fuzzy graph problems
- Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
- Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach
- Speeding up Martins' algorithm for multiple objective shortest path problems
- Novel node-ranking approach for SDN-based virtual network embedding
- Shortest paths avoiding forbidden subpaths
- The global optimal algorithm of reliable path finding problem based on backtracking method
- Optimal path selection approach for fuzzy reliable shortest path problem
- Finding the K mean-standard deviation shortest paths under travel time uncertainty
- Efficiently Generating k-Best Solutions to Procurement Auctions
- Title not available (Why is that?)
- Computing and Listing st-Paths in Public Transportation Networks
- Candidate sets for alternative routes in road networks
- Transducing Markov sequences
- Low time complexity algorithms for path computation in Cayley graphs
- Origin-destination matrix estimation problem in a Markov chain approach
- Finding the \(k\) shortest simple paths: time and space trade-offs
- Title not available (Why is that?)
- Finding a given number of solutions to a system of fuzzy constraints
- Multicriteria movement synchronization scheduling problems and algorithms
- Path flow estimator in an entropy model using a nonlinear L-shaped algorithm
- Applications of Page Ranking in P Systems
- Development of a railway out-of-gauge freight transport routing optimal method
- Fixed node determination and analysis in directed acyclic graphs of structured networks
- Computing and listing \(st\)-paths in public transportation networks
- Title not available (Why is that?)
- A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs
- Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms
- Two-best solutions under distance constraints: The model and exemplary results for matroids
- \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids
- Multi-route planning of multimodal transportation for oversize and heavyweight cargo based on reconstruction
- The first \(K\) shortest unique-arc walks in a traffic-light network
- Finding the \(k\) shortest paths in parallel
- Finding an induced path that is not a shortest path
This page was built for publication: Finding the k Shortest Paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210169)
