A new O(m+k n d) algorithm to find the k shortest paths in acyclic digraphs

DOI10.22108/TOC.2016.12602MaRDI QIDQ5134451zbMATH OpenOpenAlexFDO

Authors Mehdi Kadivar

Publication date 16 November 2020

Full work available at URL https://journals.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf

zbMATH Keywords

complexity of algorithmsranking of paths\(k\) shortest path problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Finding the k Shortest Paths
• Near-shortest and K-shortest simple paths
• Finding the k shortest simple paths
• On the k Shortest Simple Paths Problem in Weighted Directed Graphs
• An efficient implementation of an algorithm for findingK shortest simple paths

Cites work

• scientific article; zbMATH DE number 1982185 (Why is no real title available?)
• A Method for the Solution of the N th Best Path Problem
• A computational study of the capacity scaling algorithm for the maximum flow problem
• An algorithm for the ranking of shortest paths
• An efficient algorithm for K shortest simple paths
• An optimal algorithm for selection in a min-heap
• Disjoint paths in a network
• Finding \(k\) shortest simple paths in directed graphs: a node classification algorithm
• Finding the \(k\) quickest simple paths in a network
• Finding the k Shortest Paths
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths

Cited in

(4)

• scientific article; zbMATH DE number 1982185 (Why is no real title available?)
• Efficiently listing bounded length \(st\)-paths
• Enumerating \(K\) best paths in length order in DAGs
• Finding \(k\) shortest simple paths in directed graphs: a node classification algorithm

This page was built for publication: A new \(O(m+k n \log \overline{d})\) algorithm to find the \(k\) shortest paths in acyclic digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5134451)