Finding the $k$ shortest paths

David Eppstein
Proc. 35th Symp. Foundations of Computer Science, IEEE, Nov 1994, pp. 154–165
SIAM J. Computing 28(2):652–673, 1998
Tech. report 94-26, Univ. of California, Irvine, Dept. of Information and Computer Science, 1994
Mathematical Reviews 99h:05073
http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf
http://dx.doi.org/10.1137/S0097539795290477

Cited by:

On finding single-source single-destination $k$ shortest paths
Parallel Algorithms for the $k$ Shortest Paths and Related Problems
Enumerating suboptimal alignments of multiple biological sequences efficiently
New flexible approaches for multiple sequence alignment
Finding a realistic detour by AI search techniques
Detour queries in geographical databases for navigation and related algorithm animations
Optimizing systems for effective block-processing: the $k$-delay problem
Machine transliteration
On the $K$-best mode in computer chess: measuring the similarity of move proposals
Computing strictly-second shortest paths
Counting the number of paths in a graph via BDDs
Finding the $k$ shortest paths in parallel
New Approaches to Flexible Alignment of Multiple Biological Sequences
2-best solutions under distance constraints: the model and exemplary results for matroids
$k$-best solutions under distance constraints in valuated $\Delta$-matroids
Finding useful detours in geographical databases
Routing in LEO-based satellite networks.
An efficient multi-path forwarding method
Enhanced hypertext categorization using hyperlinks
Deviation algorithms for ranking shortest paths
An efficient implementation of an algorithm for finding $K$ shortest simple paths
A $K$-best paths algorithm for highly reliable communication networks
Algorithms for shortest paths and $d$-cycle problems
Dealing with additional constraints in the $k$-shortest path problem
Metabolic reconstruction using shortest paths
Translation with finite-state devices
Computing the $K$ shortest paths: A new algorithm and an experimental comparison
Automated metabolic reconstruction at the molecular level
Graph modeling of metabolism
The first $K$ minimum cost paths in a time-schedule network
A class of label-correcting methods for the $K$ shortest paths problem
A randomized algorithm for finding a path subject to multiple QoS requirements
A*Prune: An algorithm for finding $K$ shortest paths subject to multiple constraints
Selective flooding for improved quality-of-service routing
Unified approach to fuzzy graph problems
Static versus dynamic establishment of protection paths in WDM networks
Finding the $k$ shortest simple paths: a new algorithm and its implementation
Semiring frameworks and algorithms for shortest-distance problems
Time analysis for planning in a time-window network a path
Phonetic alignment and similarity
Minimum-cost QoS multicast and unicast routing in communication networks
On the difficulty of some shortest path problems
Edge distributed admission control for performance improvement in traffic engineered networks
Quality of service provisioning through traffic engineering with applicability to IP-based production networks
Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach
Multipath routing to provide quality of service in mobile ad hoc networks
An efficient algorithm for finding a path subject to two additive constraints
Path computation for traffic engineering in MPLS networks
Solving some lexicographic multi-objective combinatorial problems
Topological design and lightpath routing in WDM mesh networks: A combined approach
An efficient algorithm for sequential generation of failure states in a network with multi-mode components
New computational approaches for de novo peptide sequencing from MS/MS experiments
Efficient implementations of a delay-constrained least-cost multicast algorithm
Modeling costs of turns in route planning
Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks
Heuristic and exact algorithms for QoS routing with multiple constraints
Uncoupled method for equilibrium-based linear path flow estimator for origin-destination trip matrices
Edge distributed admission control in MPLS networks
A new traffic engineering manager for DiffServ/MPLS networks: design and implementation on an IP QoS Testbed
Coordinated target assignment and intercept for unmanned air vehicles
Multiple additively constrained path selection
LVMSR: an efficient algorithm to multicast layered video
A enumera��o dos $K$ trajectos mais curtos
A new improvement for a $K$ shortest paths algorithm
BANANAS:�an evolutionary framework for explicit and multipath routing in the internet
An efficient algorithm for the $N$-best-strings problem
Automatisches Generieren von Wanderrouten
Route specifications with a linear dual graph
Multiple path QoS routing
Alternative paths vs. inaccurate link state information in realistic network topologies
Qualitative link state dissemination control in QoS routing
Algorithms for Language Reconstruction
Resource constrained shortest paths
List detection for multi-access channels
List detection for symmetric multi-access channels
PHAROAH, a Beam Search Decoder for Phrase-Based Statistical Machine Translation Models: User Manual and Description
Noun Phrase Translation
Fault tolerance and load balancing in QoS provisioning with multiple MPLS paths
Multi-constrained optimal path selection
Vickrey prices and shortest paths: what is an edge worth?
Optimization system in networks using ACO
Traffic engineering techniques and algorithms for the internet
Appia: formalization of its topology assignment problem
Distributed optimal admission controllers for service level agreements in interconnected networks
Parametric alignment of multiple biological sequences
Improving back-transliteration by combining information sources
A lazy version of Eppstein's $K$ shortest paths algorithm
Autonomous vehicle technologies for small fixed wing UAVs
Experimental demonstration of multiple robot cooperative target intercept
Multiple UAV cooperative search under collision avoidance and limited range communication constraints
Routing and wavelength assignment in single hop all optical networks with minimum blocking
The shortest path problem with forbidden paths
In silico atomic tracing by substrate-product relationships in Escherichia coli intermediary metabolism
Design of wavelength-routed optical network topologies to minimise lightpath blocking probabilities
An exact algorithm for the robust shortest path problem with interval data
Routing reliability analysis of partially disjoint paths
A new algorithm to compute alternate paths in reliable OSPF (ROSPF)
Optimal admission controllers for service level agreements in enterprise networks
Reliable routing in MPLS networks
Bi-directional search in QoS routing
A decoupled GLS-based path flow estimator for inferring origin-destination matrices
Policy-driven traffic engineering for intra-domain quality of service provisioning
Simulation of automatic switched optical transport networks
Evaluation of novel resilience schemes in dynamic optical transport networks
Know why your access was denied: regulating feedback for usable security
Finding the K shortest hyperpaths: algorithms and applications
Finding the shortest path for quality assurance of electric components
Shortest paths in chemical kinetic applications
Route Choice in Stochastic Time-Dependent Networks: Theory, Algorithms and Computational Experience
Heuristic methods for delay-constrained least cost routing problem using $k$-shortest-path algorithms
Tosiaikainen ajoneuvoliikenteen reitinsuunnittelu (real-time vehicle traffic route planning)
SPeCRA: a stochastic performance comparison routing algorithm for LSP setup in MPLS networks
A new algorithm for $K$ shortest paths problem
From hierarchies to heterarchies: application of network optimization to design of organizational structures
On the generation of alternative solutions for discrete optimization problems with uncertain data: an experimental analysis of the penalty method
Quality of service provisioning for supporting premium services in IP networks
Selective Flooding for Better QoS Routing
Viking: a multi-spanning-tree ethernet architecture for metropolitan area and cluster networks
An algorithm for calculating the $K$ most reliable disjoint paths with a maximum number of arcs
Routing and wavelength assignment of scheduled lightpath demands in a WDM optical transport network
Routing and wavelength assignment of scheduled lightpath demands
Diverse routing of scheduled lightpath demands in an optical transport network
Dynamical Configuration of Transparent Optical Telecommunication Networks
Global mapping of nucleic acid conformational space: dinucleoside monophosphate conformations and transition pathways among conformational classes
On the $k$-simple shortest paths problem in weighted directed graphs
Cheap labor can be expensive