A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs

DOI10.22108/toc.2016.12602zbMath1463.90177OpenAlexW2766360710MaRDI QIDQ5134451

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)

Cites Work

• Unnamed Item
• K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• An algorithm for the ranking of shortest paths
• Finding the \(k\) quickest simple paths in a network
• A computational study of the capacity scaling algorithm for the maximum flow problem
• An optimal algorithm for selection in a min-heap
• A Method for the Solution of the N th Best Path Problem
• An efficient algorithm for K shortest simple paths
• Disjoint paths in a network
• Finding the k Shortest Paths
• 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