# Finding the k shortest paths

@article{Eppstein1994FindingTK, title={Finding the k shortest paths}, author={David Eppstein}, journal={Proceedings 35th Annual Symposium on Foundations of Computer Science}, year={1994}, pages={154-165} }

We give algorithms for finding the k shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these paths in a digraph with n vertices and m edges, in time O(m+n log n+k). We can also find the k shortest paths from a given source s to each vertex in the graph, in total time O(m+n log n+kn). We describe applications to dynamic programming problems including the knapsack problem, sequence alignment, and maximum… Expand

#### 721 Citations

A NEW O(m+ kn log d) ALGORITHM TO FIND THE k SHORTEST PATHS IN ACYCLIC DIGRAPHS

- 2016

We give an algorithm, called T∗, for finding the k shortest simple paths connecting a certain pair of nodes, s and t, in a acyclic digraph. First the nodes of the graph are labeled according to the… Expand

Improved algorithms for the k simple shortest paths and the replacement paths problems

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2009

It is proved that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs. Expand

Finding next-to-shortest paths in a graph

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2004

This work proves the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem of finding the next-to-shortest paths in a graph. Expand

The next-to-shortest path problem on directed graphs with positive edge weights

- Mathematics, Computer Science
- Networks
- 2015

This article considers the version where G is directed and all edge weights are positive, and if G is planar, an On3-time algorithm is proposed, where n is the number of vertices of G. Expand

Parallel Algorithms for the K Shortest Paths and Related Problems Parallel Algorithms for the K Shortest Paths and Related Problems

- 1996

A parallel algorithm is developed to nd the k shortest paths between pairs of vertices in an edge-weighted directed graph. The concurrent-read exclusive-write PRAM is used as the model of… Expand

A new improvement for a K shortest paths algorithm

- Computer Science
- 2001

An improvement for a known deletion path algorithm is presented which results in the improvement of its execution time complexity when the worst case analysis is considered. Expand

Multiple Source Replacement Path Problem

- Computer Science, Mathematics
- PODC
- 2020

For an undirected and unweighted graph, (Malik, Mittal, and Gupta, Operation Research Letters, 1989) and (Hershberger and Suri, FOCS 2001) designed an algorithm that solves the replacement path problem in Õ (m + n) time1. Expand

A nonenumerative algorithm to find the k longest (shortest) paths in a DAG

- Computer Science, Mathematics
- ArXiv
- 2013

A novel and efficient algorithm to find the k longest (shortest) paths between sources and sinks in a directed acyclic graph (DAG) based on the Valued-Sum-of-Product (VSOP) tool, which is an extension of Zero-suppressed Binary Decision Diagrams (ZBDDs). Expand

K⁎: A heuristic search algorithm for finding the k shortest paths

- Mathematics, Computer Science
- Artif. Intell.
- 2011

We present a directed search algorithm, called K^@?, for finding the k shortest paths between a designated pair of vertices in a given directed weighted graph. K^@? has two advantages compared to… Expand

Efficiently Listing Bounded Length st-Paths

- Mathematics, Computer Science
- IWOCA
- 2014

This work considers a different parameterization for this problem: instead of bounding the number of st-paths output, the authors bound their length, and proposes new non-trivial algorithms matching the time complexity of the classic algorithms but using only \(O(m+n)\) space. Expand

#### References

SHOWING 1-10 OF 87 REFERENCES

An efficient algorithm for K shortest simple paths

- Mathematics, Computer Science
- Networks
- 1982

This article gives an efficient algorithm for obtaining K shortest simple paths between two specified nodes in an undirected graph G with non-negative edge lengths, which is better than those realized by existing algorithms. Expand

An algorithm for finding the k quickest paths in a network

- Mathematics, Computer Science
- Comput. Oper. Res.
- 1993

The problem considered in this paper is to find the first k quickest looping paths from the source to the sink, and an algorithm with time complexity of O(m 2 + (m + k)n log n + k 3 2 log k) is developed. Expand

Finding a minimum weight K-link path in graphs with Monge property and applications

- Computer Science
- SCG '93
- 1993

This work gives an efficient algorithm for finding the minimum weight K-link path between a given pair of vertices for any given K, using some properties of DAGs with Monge property together with a refined parametric search technique. Expand

Finding the k Quickset Simple Paths in a Network

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1994

The problem considered in this paper is to find the first k quickest simple paths for a given pair of nodes, and an algorithm is designed. Expand

Faster shortest-path algorithms for planar graphs

- Mathematics, Computer Science
- STOC '94
- 1994

The shortest-path algorithm yields an $O(n^{4/3} \log n)$-time algorithm for finding a perfect matching in a planar bipartite graph and a similar improvement is obtained for maximum flow in a directed planar graph. Expand

Scaling algorithms for the shortest paths problem

- Mathematics, Computer Science
- SODA '93
- 1993

An O((square root of n)m log N) algorithm for the single-source shortest paths problem with integral arc lengths is given, which improves previous bounds for the problem. Expand

Solvingk-shortest and constrained shortest path problems efficiently

- Mathematics
- 1989

In this paper, we examine the problems of finding thek-shortest paths, thek-shortest paths without repeated nodes, and the shortest path with a single side constraint between an origin and… Expand

Algorithms for the quickest path problem and the enumeration of quickest paths

- Mathematics, Computer Science
- Comput. Oper. Res.
- 1991

An alternative algorithm for the single pair quickest path problem with same time complexity and less space requirement is developed and an algorithm to enumerate the first m quickest paths to send a given amount of data with time complexity O(rmne + rmn2 log n) time is developed. Expand

Trans-dichotomous algorithms for minimum spanning trees and shortest paths

- Mathematics
- FOCS 1990
- 1990

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a… Expand

Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees

- Mathematics, Computer Science
- [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science
- 1991

Ambivalent data structures are presented for several problems on undirected graphs and used in finding the k smallest spanning trees of a weighted undirecting graph in O(m log beta (m,n)+min(k/sup 3/2/, km/sup 1/2/)) time, where m and n are understood to be the current number of edges and vertices, respectively. Expand