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

DOI10.22108/TOC.2016.12602zbMATH Open1463.90177OpenAlexW2766360710MaRDI QIDQ5134451FDOQ5134451

Authors: Mehdi Kadivar 

Publication date: 16 November 2020

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

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

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

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

Cited In (4)

• Title not available (Why is that?)
• 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)