Finding the k Shortest Paths

DOI10.1137/S0097539795290477zbMath0912.05057MaRDI QIDQ4210169

David Eppstein

Publication date: 21 September 1998

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

zbMATH Keywords

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

Mathematics Subject Classification ID

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

94C15: Applications of graph theory to circuits and networks

05C20: Directed graphs (digraphs), tournaments

Related Items

Applications of Page Ranking in P Systems, Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms, On a Class of Interval Data Minmax Regret CO Problems, The shortest path problem with forbidden paths, Solving the constrained shortest path problem using random search strategy, A heuristic for optimizing stochastic activity networks with applications to statistical digital circuit sizing, Finding next-to-shortest paths in a graph, \(k\)-shortest routing of trains on shunting yards, 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, Splitting (complicated) surfaces is hard, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems, A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool, Multi-objective evacuation routing in transportation networks, An efficient algorithm to find next-to-shortest path on permutation graphs, The one-dimensional cutting stock problem with due dates, 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, Finding the first \(K\) shortest paths in a time-window network., Solving some lexicographic multi-objective combinatorial problems, Unified approach to fuzzy graph problems, Finding the \(K\) shortest hyperpaths, Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach, An exact algorithm for the robust shortest path problem with interval data, Finding \(K\) shortest looping paths in a traffic-light network, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, On the cardinality of the Pareto set in bicriteria shortest path problems, A decision-theoretic approach to robust optimization in multivalued graphs, Constructing the nearly shortest path in crossed cubes, The first \(K\) shortest unique-arc walks in a traffic-light network, 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, The most probable annotation problem in HMMs and its application to bioinformatics, Choquet-based optimisation in multiobjective shortest path and spanning tree problems, Providing Evidence of Likely Being on Time: Counterexample Generation for CTMC Model Checking, A novel single source shortest path algorithm, Efficiently Generating k-Best Solutions to Procurement Auctions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for ranking paths that may contain cycles
• Algorithms for the quickest path problem and the enumeration of quickest paths
• An algorithm for finding the \(k\) quickest paths in a network
• Semirings and path spaces
• Finding the \(k\) quickest simple paths in a network
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• Algorithms for proximity problems in higher dimensions
• An optimal algorithm for selection in a min-heap
• 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
• On a routing problem
• Faster algorithms for the shortest path problem
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Implementation of algorithms forK shortest loopless paths
• An efficient algorithm for K shortest simple paths
• Disjoint paths in a network
• Comment on a computing the k shortest paths in a graph
• All paths in an activity network
• Iterative methods for determining the k shortest paths in a network
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• 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
• Scaling Algorithms for the Shortest Paths Problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Separator based sparsification for dynamic planar graph algorithms
• An Appraisal of Some Shortest-Path Algorithms
• Finding the K Shortest Loopless Paths in a Network
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A Note on an Algebra for the k Best Routes in a Network
• Faster shortest-path algorithms for planar graphs