K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths

DOI10.1016/j.artint.2011.07.003zbMath1238.68148OpenAlexW2122516422MaRDI QIDQ420803

Stefan Leue, Husain Aljazzar

Publication date: 23 May 2012

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2011.07.003

zbMATH Keywords

heuristic search\(k\)-shortest-paths problemK\(^{\ast}\)on-the-fly search

Mathematics Subject Classification ID

Paths and cycles (05C38) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Robust identification of nonlinear state-dependent impulsive switched system with switching duration constraints ⋮ Minimal counterexamples for linear-time probabilistic verification ⋮ Counterexample Generation for Discrete-Time Markov Models: An Introductory Survey ⋮ Multi-route planning of multimodal transportation for oversize and heavyweight cargo based on reconstruction ⋮ A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs ⋮ Learning to Approximate Industrial Problems by Operations Research Classic Problems

Uses Software

• PRISM
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• An optimal algorithm for selection in a min-heap
• Generalized best-first search strategies and the optimality of A*
• Finding the k Shortest Paths
• Finding the K Shortest Loopless Paths in a Network
• Counterexamples in Probabilistic Model Checking
• Formal Modeling and Analysis of Timed Systems

This page was built for publication: K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths